题目描述
国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源
于易经的思想，棋盘是一个 $8 * 8$ 大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主人公小Q，
正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定
将棋盘扩大以适应他们的新规则。小Q找到了一张由 $N * M$ 个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种
颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。不过小Q还没有决定是找
一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他
希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？
输入格式
第一行包含两个整数N和M，分别表示矩形纸片的长和宽。接下来的N行包含一个N * M的01矩阵，表示这张矩形
纸片的颜色（0表示白色，1表示黑色）。
输出格式
包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋
盘的面积（注意正方形和矩形是可以相交或者包含的）。
样例输入
3 3
1 0 1
0 1 0
1 0 0
样例输出
4
6
说明
N, M ≤ 2000
Solution
这道题求正方形很好求，状态转移方程f[i][j]=min{f[i][j-1],f[i-1][j-1],f[i-1][j]}；但长方形很难求，我本知道要用悬线法，但我仍然硬推方程，最后推了一个小时没推出来，被逼用悬线法。
Code
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 2002
using namespace std;
int max(int a,int b) {
if(a>b) return a;
else return b;
}
int min(int a,int b) {
if(a<b) return a;
else return b;
}
int a[MAXN][MAXN],f[MAXN][MAXN],l[MAXN][MAXN],r[MAXN][MAXN],L[MAXN][MAXN],R[MAXN][MAXN],h[MAXN][MAXN],n,m,ans=0,ansj=0,tmp;
int solve() {
memset(f,0,sizeof(f));
memset(l,0,sizeof(f));
memset(r,0,sizeof(f));
memset(L,0,sizeof(f));
memset(R,0,sizeof(f));
memset(h,0,sizeof(f));
for (int i=1; i<=n; i++) {
tmp=0;
for (int j=1; j<=m; j++){
if (a[i][j]){
l[i][j]=tmp;
}
else {
tmp=j;
L[i][j]=0;
}
}
tmp=m+1;
for (int j=m; j>=1; j--){
if (a[i][j]) {
r[i][j]=tmp;
}
else {
tmp=j;
R[i][j]=m+1;
}
}
}
for (int i=1; i<=m; i++) {
R[0][i]=m+1;
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
if (a[i][j]) {
h[i][j]=h[i-1][j]+1;
L[i][j]=max(L[i-1][j],l[i][j]);
R[i][j]=min(R[i-1][j],r[i][j]);
ansj=max(ansj,h[i][j]*(R[i][j]-L[i][j]-1));
}
}
}
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
scanf("%d",&a[i][j]);
f[i][j]=1;
if(i>=2&&j>=2) {
if(((a[i][j-1]^a[i][j])==1)&&(a[i-1][j-1]==a[i][j])&&(a[i-1][j]==a[i][j-1])) {
f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
ans=max(ans,f[i][j]*f[i][j]);
}
}
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if((i&1)==(j&1)) {
a[i][j]^=1;
}
}
}
solve();
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
a[i][j]^=1;
}
}
solve();
printf("%d\n%d",ans,ansj);
return 0;
}
|
