Largest Square Submatrix with Uniform Values

Given an \( n \times n \) matrix, your task is to determine the side length of the largest square submatrix in which every element is identical.

To solve this problem, you can use a dynamic programming approach. Let \( dp(i,j) \) denote the side length of the largest square submatrix ending at cell \( (i,j) \). Then, for \( i,j \ge 1 \), if the current cell has the same value as its left, top, and top-left neighbors, the recurrence relation is:

\( dp(i,j)=\min\{dp(i-1,j),\;dp(i,j-1),\;dp(i-1,j-1)\}+1 \)

Otherwise, \( dp(i,j)=1 \). For cells on the top row or left column, the value is \( 1 \) by definition.

You are required to implement a solution that reads the matrix from standard input and outputs the desired result to standard output.

inputFormat

The first line of input contains a single integer \( n \), the size of the matrix. This is followed by \( n \) lines, each containing \( n \) space-separated integers representing the rows of the matrix.

outputFormat

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

4
1 1 1 2
1 1 1 2
1 1 1 2
3 3 2 2

3