Largest Square Sub-grid

This problem requires you to determine the side length of the largest square sub-grid within a given grid that contains only 1s. You are given an n x n grid consisting of 0s and 1s. A square sub-grid is defined as a contiguous block of cells that forms a square.

The optimal solution uses dynamic programming. Define a DP table dp such that for each cell (i, j):

$$dp_{ij} = \begin{cases} \min(dp_{i-1,j},\;dp_{i,j-1},\;dp_{i-1,j-1})+1 & \text{if } grid[i][j]=1,\\ 0 & \text{if } grid[i][j]=0. \end{cases} $$

The answer is the maximum value in the DP table, which represents the side length of the largest square composed entirely of 1s.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

• The first line contains a single integer n representing the size of the grid (n x n).
• The next n lines each contain n space-separated integers (either 0 or 1), representing the elements of each row of the grid.

outputFormat

Output a single integer to standard output (stdout) which is the side length of the largest square sub-grid that contains only 1s.## sample

4
1 1 1 0
1 1 1 0
1 1 1 1
0 0 1 1

3

</p>