A field with a True value represents a 1x1
square on its own. If a field has free fields on its left, top, and top-left, then it’s the bottom-right corner of a 2x2
square. If those three fields are all bottom-right corners of a 5x5
square, then their overlap, plus the queried field being free, form a 6x6 square. We can use this logic to solve this problem. That is, we define the relation of size[x, y] = min(size[x-1, y], size[x, y-1], size[x-1, y-1]) + 1 for every free field. For an occupied field, we can set size[x,y] = 0
, and it will fit our recursive relation perfectly. Now, size[x, y]
represents the largest square for which the field is the bottom-right corner. Tracking the maximum number achieved will give us the answer to our problem.
FUNCTION square_size(board)
M = board.height()
N = board.width()
size = Matrix[M + 1, N + 1]
FOR i IN [0..M]
size[i, 0] = 0
END FOR
FOR i IN [0..N]
size[0, i] = 0
END FOR
answer = 0
FOR i IN [0..M]
FOR j IN [0..N]
size[i+1, j+1] = max(size[i, j+1], size[i+1, j], size[i, j]) + 1
answer = max(answer, size[i+1, j+1])
END FOR
END FOR
RETURN answer