Largest Square of Trees

You are given a rectangular forest grid consisting of n rows and m columns. Each cell in the grid is represented by a character: '1' indicates the presence of a tree and '0' indicates an empty cell. Your task is to find the side length of the largest square region in the forest where every cell contains a tree.

This problem can be solved using dynamic programming. Let \(dp[i][j]\) denote the side length of the largest square that ends at cell \((i,j)\) (with \(i\) and \(j\) being 0-indexed). The recurrence relation is given by:

[ \text{dp}[i][j] = \begin{cases} 1, & \text{if } i = 0 \text{ or } j = 0 \text{ and } \text{forest}[i][j] = '1' \ \min{\text{dp}[i-1][j],,\text{dp}[i][j-1],,\text{dp}[i-1][j-1]} + 1, & \text{if } \text{forest}[i][j] = '1' \ 0, & \text{if } \text{forest}[i][j] = '0' \end{cases} ]

The answer is the maximum value in the dp table.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers n and m, representing the number of rows and columns respectively.
• The following n lines each contain a string of length m consisting only of the characters '0' and '1', representing a row of the forest.

outputFormat

Output an integer to stdout representing the side length of the largest square sub-grid containing only trees ('1').

5 6
110001
110001
111101
000011
000011

2