Finding the Largest Square in a Binary Matrix

You are given a binary matrix with m rows and n columns. Each element in the matrix is either 0 or 1. Your task is to find the area of the largest square in the matrix that contains only 1s.

If there is no such square, your program should return 0.

The problem can be formulated using a dynamic programming approach, where for each cell in the matrix, you compute the side length of the largest square having that cell as the bottom-right corner. The recurrence relation for the dynamic programming solution is given by:

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

The area of the largest square is then \(\text{side}^2\), where \(\text{side}\) is the maximum value found in the dp table.

inputFormat

The first line contains two integers m and n separated by a space, representing the number of rows and columns of the matrix, respectively.

The next m lines each contain n space-separated integers (either 0 or 1) representing the matrix.

outputFormat

Output a single integer: the area of the largest square that contains only 1s. If no such square exists, output 0.

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

4