Given a m*n array only containing 0s and 1s, some blocks in the array are occupied by all 1s, find the maximum square which does not cross these blocks
row[i][j] counts the contiguous 0s from array[i][j] to left boundary
col[i][j] counts the contiguous 0s from array[i][j] to up boundary
sqr[i][j] counts the length of maximum all 0s square which takes array[i][j] as right-down corner
for(int i=0;i < m;i++)
for(int j=0;j < n;j++)
sqr[i][j]=min{sqr[i-1][j-1]+1,row[i][j],col[i][j]}
sqr[0][j]=1-array[0][j], j=1…N
sqr[i][0]=1-array[i][0],i=1…M
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment