Largest Square Submatrix Area

You are given an m x n binary matrix. Your task is to compute the area of the largest square submatrix that consists entirely of 1s. A square submatrix means that the submatrix has the same number of rows and columns. Use dynamic programming techniques to achieve an efficient solution with a time complexity of O(m·n).

Hint: Use a 2D dp array where dp[i][j] represents the side length of the largest square submatrix ending at cell (i,j). The recurrence is: \[ dp[i][j] = \min\{ dp[i-1][j], \; dp[i][j-1], \; dp[i-1][j-1] \} + 1 \] if the current element is 1, and 0 otherwise. The answer is the square of the maximum side length found.

inputFormat

The first line contains two integers, m and n, separated by a space, where m is the number of rows and n is the number of columns. This is followed by m lines, each containing n integers (0 or 1) separated by spaces, representing the matrix.

Example:

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

outputFormat

Output a single integer representing the area of the largest square submatrix that contains only 1s.

Example:

4

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

4