Largest Identical Square Subgrid

Given an n x m grid of integers, the task is to determine the side length of the largest square subgrid in which all the values are identical. A square subgrid is a contiguous block of cells forming a square, and its side length is defined as the number of cells along one edge.

The problem can be approached using dynamic programming. For each cell (i, j) in the grid, we can define dp[i][j] as the side length of the largest square subgrid ending at that cell in which all values are the same. The recurrence can be written as:

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

if the current cell has the same value as its top, left, and top-left neighbors; otherwise, dp[i][j] is 1.

This problem tests your ability to implement efficient dynamic programming solutions and process grid-based inputs.

inputFormat

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

This is followed by n lines, each containing m integers separated by spaces, representing the grid values.

outputFormat

Output a single integer representing the side length of the largest square subgrid in which all values are identical.

5 6
1 1 1 2 2 2
1 1 1 2 2 2
1 1 1 2 2 2
3 3 3 4 4 4
3 3 3 4 4 4

3