Largest Square of Buildings

You are given a 2D grid of integers, where each cell is either 0 (empty) or 1 (building). Your task is to find the side length of the largest square subgrid that contains only buildings.

For each cell in the grid, if it contains a building (1), you can form a square ending at that cell. The side length of the largest square ending at grid cell \( (i, j) \) can be computed using the following recurrence:

[ dp[i][j] = \min{dp[i-1][j],; dp[i][j-1],; dp[i-1][j-1]} + 1 ]

If a cell contains 0, then no building square can end at that cell. The answer is the maximum value among all cells in the dynamic programming table.

If the grid is empty, the answer should be 0.

inputFormat

The input is given via standard input (stdin) and is formatted as follows:

1. The first line contains two integers \(N\) and \(M\), representing the number of rows and columns of the grid respectively.
2. The following \(N\) lines each contain \(M\) space-separated integers (each either 0 or 1) representing the grid.

outputFormat

Output a single integer to standard output (stdout) representing the side length of the largest square composed solely of 1s.

5 6
0 1 1 0 1 1
1 1 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1
0 1 1 1 1 0

3