Looking at this, I realized that I need to reset lastRight=lastDown=n inside the first loop, before the for(j=n-1 loop
On Jan 16, 2:59 pm, Don <[email protected]> wrote: > int countRight[n][n]; > int countDown[n][n]; > > int i,j,s; > int bestI, bestJ, max=0; > int lastRight = n; > int lastDown = n; > > // Start by setting countRight[i][j] to the number of consecutive > black pixels starting at (i,j) and moving right > // and countDown[i][j] to the number of consecutive black pixels > starting at (i,j) and moving down > for(i = 0; i < n; ++i) > for(j = n-1; j >= 0; --j) > { > if (m[i][j] == white) lastRight = j; > if (m[j][i] == white) lastDown = j; > countRight[i][j] = lastRight - j; > countDown[j][i] = lastDown - j; > } > > // Now look for largest square with top left corner at (i,j) > for(i = 0; (i+max) < n; ++i) > for(j = 0; (j+max) < n; ++j) > for(s = Min(countRight[i][j], countDown[i][j]); s > max; --s) > if ((countRight[i+s][j] >= s) && (countDown[i][j+s] >= s)) > { > bestI = i; bestJ = j; max = s; > } > > Don > > On Jan 16, 2:08 pm, marti <[email protected]> wrote: > > > > > > > > > Imagine there is a square matrix with n x n cells. Each cell is either > > filled with a black pixel or a white pixel. Design an algorithm to find the > > maximum subsquare such that all four borders are filled with black pixels; > > optimize the algorithm as much as possible --
