Square (Editorial)

Let us define a two-dimensional array $dp$, where

• dp[i][j] denotes the side length of the largest square consisting entirely of ones, with its bottom-right corner at cell $(i,j)$.

Let the array $m$ represent the given grid.

Base cases

• If m[i][j] = 0 (the cell is defective), then no square can end at cell $(i,j)$. Therefore, dp[i][j] = 0;

• If the cell lies on the boundary (i = 0 or j = 0) and m[i][j] = 1, then only a square of size $1$ is possible. Therefore, dp[i][j] = 1

DP transitions

Assume that m[i][j] = 1. Consider the following cases:

1. Suppose that m[i - 1][j] = m[i][j - 1] = k. Then the value of dp[i][j] depends on the state of the cell m[i - k][j - k]:

   • If m[i - k][j - k] = 1, then the entire square with corners at (i - k, j - k) and $(i,j)$ consists only of ones, so dp[i][j] = k + 1.

   • If m[i - k][j - k] = 0, then the square cannot be extended, and dp[i][j] = k.

   

2. If m[i - 1][j] \ne m[i][j - 1], then the value of dp[i][j] is determined as

Summarizing the above, we obtain the general formula:

Example

Consider the second test case. Let us construct the $dp$ array for it.

There are two largest squares of size 3 \cdot 3. The product of the maximum square size and the number of its occurrences is 3 \cdot 2 = 6.

Algorithm implementation

Declare the array $dp$.

#define MAX 1010
int dp[MAX][MAX];

Read the value of $n$. The variable $size$ stores the side length of the largest square, while $cnt$ stores the number of such squares in the given grid. Initialize the $dp$ array with zeros.

scanf("%d", &n);
memset(dp,0,sizeof(dp));
size = cnt = 0;

Iterate over the elements of the $dp$ array row by row: rows in increasing order, and within each row, columns also in increasing order.

  for(i = 1; i <= n; i++)
  for(j = 1; j <= n; j++)
  {
    scanf("%d",&val);

Assume that all values of the $dp$ array up to cell $(i,j)$ have already been computed. Read the next value val = m[i][j]. The input matrix is not stored entirely in memory; instead, it is processed on the fly.

Since the $dp$ array is initially initialized with zeros, when val = 0, the value dp[i][j] automatically remains zero.

    if (val == 1)
    {
      dp[i][j] = min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;

Update the values of $size$ and $cnt$ based on the current square of size dp[i][j].

      if (dp[i][j] == size) cnt++;
      if (dp[i][j] > size) {size = dp[i][j]; cnt = 1;}
    }
  }

Print the answer.

printf("%lld\n",1LL * size * cnt);