Largest Square Subgrid

You are given a grid of size \(n \times m\) consisting of integers 0 and 1. A cell with 0 represents a traversable cell, and a cell with 1 represents an obstacle. Your task is to determine the side length of the largest square subgrid that can be formed using only traversable cells (i.e. cells with 0).

The problem can be solved using dynamic programming. Let \(dp[i][j]\) represent the side length of the largest square whose bottom-right corner is at \((i,j)\). The transition for \(dp[i][j]\) when the cell is traversable (i.e., 0) is given by:

[ dp[i][j] = \min(dp[i-1][j],, dp[i][j-1],, dp[i-1][j-1]) + 1 ]

If a cell is not traversable (i.e., 1), set \(dp[i][j] = 0\). The answer is the maximum value found in the \(dp\) table.

inputFormat

The input is given from standard input (stdin) and it contains:

• The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 1000) \) representing the number of rows and columns of the grid.
• The next \(n\) lines each contain \(m\) space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer to standard output (stdout) which is the side length of the largest square subgrid consisting entirely of 0's.

4 5
1 0 1 0 0
1 0 0 0 0
1 0 0 1 0
0 1 1 1 0

2