Largest Square Area

You are given a grid with n rows and m columns. Each cell of the grid contains either a 0 or a 1. Your task is to determine the area of the largest square sub-grid that is completely filled with 1's.

Consider the grid as a 2D matrix where the cell in the i^th row and j^th column is denoted by \(grid[i][j]\). You need to find the square (i.e. a contiguous submatrix) such that every cell in the square equals 1, and then output the area of that square.

Hint: Use dynamic programming to compute the side lengths of possible squares at each cell. The recurrence relation for a cell \(dp[i][j]\) when \(grid[i][j] = 1\) 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.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains two integers \(n\) and \(m\), representing the number of rows and columns in the grid.
2. The following \(n\) lines each contain \(m\) integers (each being 0 or 1) separated by spaces, representing the grid.

outputFormat

Output a single integer to standard output (stdout) representing the area of the largest square sub-grid that is entirely filled with 1's. If there is no such square, 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