7757. Square
Jian-Jia has a piece of metal material and wants to cut a
square from it. The material is represented as an n × n grid, and cuts
can only be made along the grid boundaries.
Each cell of the grid is either usable or defective. Jian-Jia
aims to cut the largest possible square that contains no defective cells. After
determining the maximum possible size of such a square, he also wants to know
how many different ways this square can be cut from the material.
Finally, Jian-Jia reports the product of the maximum size and
the number of such possible ways.
Consider a 6 × 6 material, as shown in the figure below. The black cells are
defective. The largest square that can be cut has size 3 × 3, and there are two possible ways
to obtain it (shown as the red and green squares). Therefore, Jian-Jia reports
the product 3 * 2 = 6.
Your
task is to determine the maximum size of a square that can be cut from the
given material, as well as the number of distinct ways to obtain such a square.
Output the product of these two values.
Input. The first
line contains one integer n (1
≤ n ≤ 1000) – the size of
the material.
Each of the next n lines
contains n integers. A value of 1 indicates that the corresponding cell is usable, while
0 indicates that it is defective.
Output.
Print one integer – the product of the size of the largest
square without defective cells and the number of its possible positions in the
material.
|
Sample
input 1 |
Sample
output 1 |
|
6 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 |
18 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
6 0 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 |
6 |
SOLUTION
dynamic programming
Algorithm analysis
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] ≠ m[i][j – 1], then the value of dp[i][j]
is determined
as
dp[i][j]
= min(dp[i – 1][j], dp[i][j – 1]) + 1
Summarizing the above, we
obtain the general formula:
dp[i][j]
= min(dp[i – 1][j], dp[i][j – 1], dp[i – 1][j – 1]) + 1
Example
Consider the second test
case. Let us construct the dp array for it.
There are two largest
squares of size 3 * 3. The product of the maximum square size and the number of its
occurrences is 3 * 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);