Largest Square Playground

You are given a farm represented as a grid with m rows and n columns. Each cell in the grid is either empty (represented by 0) or contains a tree (represented by 1). Your task is to determine the side length of the largest square playground that can be built on empty cells.

More formally, let \( grid[i][j] \) denote the value in the cell at row \( i \) and column \( j \). A cell is empty if \( grid[i][j] = 0 \). The problem is to find the maximum integer \( k \) such that there exists a \( k \times k \) sub-grid where every cell is 0. A dynamic programming approach can solve this by using the recurrence:

[ dp[i][j] = \begin{cases} 1, & \text{if } i = 0 \text{ or } j = 0 \text{ and } grid[i][j] = 0, \ \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, & \text{if } grid[i][j] = 0, \ 0, & \text{if } grid[i][j] = 1. \end{cases} ]

The answer is then the maximum value found in the dp table.

inputFormat

The first line of input contains two integers m and n representing the number of rows and columns of the grid.

Each of the next m lines contains n integers separated by spaces. Each integer is either 0 or 1, where 0 represents an empty cell and 1 represents a tree.

outputFormat

Output a single integer representing the side length of the largest square that can be formed using only empty cells.

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

2