Largest Empty Square Subgrid

You are given a grid with N rows and M columns. Each cell of the grid is either empty or filled. The grid is represented by N strings of length M consisting of the characters '0' and '1', where '0' indicates an empty cell and '1' indicates a filled cell.

Your task is to find the side length of the largest square sub-grid that contains only empty cells.

The sub-grid should be contiguous, and its side length is defined as the number of cells along one of its sides. Using dynamic programming, you can solve this problem in O(N×M) time.

More formally, if we define dp[i][j] as the side length of the largest square whose bottom-right corner is at cell (i, j), then for every empty cell (i.e., where the grid cell's value is '0') the recurrence is given by:

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

Consider that cells on the top row or leftmost column have a maximum square side of \(1\) if they are empty.

Return the maximum value of dp[i][j] over all cells, which represents the side length of the largest square of empty cells.

inputFormat

The input is given from stdin with the following format:

N M
row1
row2
...
rowN

Where:

• N and M are two integers representing the number of rows and columns respectively.
• Each row is a string of length M, containing characters '0' and '1'.

outputFormat

Output a single integer to stdout: the side length of the largest square sub-grid that contains only empty cells.

## sample

5 6
101001
100000
101011
100001
101110

2