Largest Square of 1s

You are given a binary matrix with R rows and C columns. Your task is to find the area of the largest square sub-matrix that contains only the digit 1.

More formally, let \(dp[i][j]\) be the side length of the largest square whose bottom-right corner is at \( (i,j) \). Then for every cell with value 1, the recurrence is given by:

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

The answer is the square of the maximum side length found.

This is a typical dynamic programming problem that tests your ability to analyze and compute subproblems efficiently. Good luck!

inputFormat

The first line of the input contains two integers R and C, representing the number of rows and columns of the matrix, respectively. Each of the next R lines contains C space-separated integers (each is either 0 or 1).

outputFormat

Output a single integer that denotes the area of the largest square sub-matrix that consists entirely of 1s.## sample

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

9