Problem Statement
回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为 $01$ 矩阵（$0$ 表示对应位置无鱼，$1$ 表示对应位置有鱼）有助于决定吃鱼策略。
在代表池子的 $01$ 矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。
猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？
第一行有两个整数 $n$ 和 $m$（$n,m≥1$），描述池塘规模。接下来的 $n$ 行，每行有 $m$ 个数字（非 $0$ 即 $1$）。每两个数字之间用空格隔开。
Output
只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。
1
2
3
4
5
|
4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0
|
Sample Output
Explanation of example
右上角的
Constraints
- 对于 $30%$ 的数据，有 $1\le n,m\le 100$；
- 对于 $60%$ 的数据，有 $1\le n,m\le 1000$；
- 对于 $100%$ 的数据，有 $1\le n,m\le 2500$。
Solving
我们可以利用搜索+二维前缀和的知识在时间复杂度为O(N$^{3}$)内解决这个问题
让我们先补充一下关于二维前缀和的知识：
一、二维前缀和的定义
对于一个二维数组 $a$，其二维前缀和数组 $sum$ 的定义为：
$$
sum_{i,j}=\sum_{x = 1}^{i}\sum_{y = 1}^{j}a_{x,y}
$$
$sum_{i,j}$ 表示原数组 $a$ 中左上角为 $(1,1)$，右下角为 $(i,j)$ 的矩形区域内所有元素的和。
二、二维前缀和的计算方法
假设我们有一个二维数组 $a$，我们可以通过以下方式计算其二维前缀和数组
1
2
3
4
5
6
7
8
9
|
const int maxn = 1005;
int a[maxn][maxn], sum[maxn][maxn];
int n, m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
}
|
上述代码中，对于位置 $(i, j)$ 的二维前缀和 $sum[i][j]$ 的计算方式是： - $sum[i - 1][j]$ 表示 $(i - 1, j)$ 的前缀和，它包含了前 $i - 1$ 行，第 $j$ 列的元素和。 - $sum[i][j - 1]$ 表示 $(i, j - 1)$ 的前缀和，它包含了第 $i$ 行，前 $j - 1$ 列的元素和。 - $sum[i - 1][j - 1]$ 被重复计算了一次，所以需要减去。 - 最后加上当前元素 $a[i][j]$。
三、计算子矩阵元素和
$$
s = sum_{x_2,y_2}-sum_{x_2,y_1 - 1}-sum_{x_1 - 1,y_2}+sum_{x_1 - 1,y_1 - 1}
$$
代码实现如下：
1
2
3
|
int subMatrixSum(int x1, int y1, int x2, int y2) {
return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}
|
具体实现可以模拟为在一个矩阵中分割出子矩阵。
四、解题思路
综上，我们只需要遍历整个矩阵，每扫描到1就以该点为一个顶点就斜向两边扩张正方形的边长（在斜向元素也等于1的情况下），同时计算这个子矩阵的值是否等于边长，如果等于边长则证明这个正方形子矩阵内除了对角线之外的元素均为0，满足题意，只要不断搜索、更新最大边长即可在$O(n^2m + nm^2)$时间复杂度内解决问题。
五、解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int M = 0;
const int N = 2501;
int mp[N][N],prefix[N][N];
int ans = 0;
int n,m;
int t;
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);
cin >> n >> m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin >> mp[i][j];
prefix[1][1] = mp[1][1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + mp[i][j];//预处理二维前缀和数组
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j])//如果为1
{
int curans1 = 1;
for(int k=1;i+k<=n&&j+k<=m&&mp[i+k][j+k];k++)//矩阵向右下扩张
{ //计算扩张后的矩阵元素和
if(prefix[i+k][j+k]-prefix[i+k][j-1]-prefix[i-1][j+k]+prefix[i-1][j-1]==k+1) curans1++;
else break;//一旦不能继续满足则没有继续搜索的必要，直接break
}
ans = max(ans,curans1);
int curans2 = 1;
for(int k=1;i+k<=n&&j-k>0&&mp[i+k][j-k];k++)//矩阵向左下扩张
{
if(prefix[i+k][j]-prefix[i+k][j-k-1]-prefix[i-1][j]+prefix[i-1][j-k-1]==k+1) curans2++;
else break;
}
ans = max(ans,curans2);//不断更新最大值
}
}
}
cout << ans;
return 0;
}
|