Largest Square Subgrid

You are given a grid with n rows and m columns. Each cell of the grid contains either 0 or 1. Your task is to determine the side length of the largest square subgrid that consists entirely of 1s.

This problem can be solved efficiently using dynamic programming. For each cell in the grid, you can compute the maximum size of a square that can be formed ending at that cell. The recurrence is given by:

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

Output the maximum value in the DP table which represents the side length of the largest square.

inputFormat

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

• The first line contains two integers n and m (the number of rows and columns respectively).
• The next n lines each contain m integers separated by spaces, where each integer is either 0 or 1 representing the grid.

outputFormat

Output a single integer, which is the side length of the largest square subgrid that contains only 1s. The output is written to the standard output (stdout).

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

2