题目描述：
国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个 $8\times 8$ 大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。
而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。
小Q找到了一张由 $N\times M$ 个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。
不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。
于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？
输入格式
包含两个整数 $N$ 和 $M$ ，分别表示矩形纸片的长和宽。接下来的 $N$ 行包含一个 $N\times M$ 的01矩阵，表示这张矩形纸片的颜色（0表示白色，1表示黑色）。
输出格式
包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。
数据范围：
$1\le N,M \le 2000$
题解：
经典悬线法，但是需要注意的是需要 $01$ 相间隔，只有与上次的不同才能更新。
代码：
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
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 2e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int matrix[maxn][maxn];
int lef[maxn][maxn];
int righ[maxn][maxn];
int heigh[maxn][maxn];
void solve()
{
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= n; ++i)
{
lef[i][1] = 1;
for (int j = 2; j <= m; ++j)
{
if (matrix[i][j] == !matrix[i][j - 1])
lef[i][j] = lef[i][j - 1] + 1;
else
lef[i][j] = 1;
}
righ[i][m] = 1;
for (int j = m - 1; j >= 1; --j)
{
if (matrix[i][j] == !matrix[i][j + 1])
righ[i][j] = righ[i][j + 1] + 1;
else
righ[i][j] = 1;
}
for (int j = 1; j <= m; ++j)
{
heigh[i][j] = 1;
if (i >= 2 && matrix[i][j] == !matrix[i - 1][j])
{
heigh[i][j] = heigh[i - 1][j] + 1;
lef[i][j] = min(lef[i][j], lef[i - 1][j]);
righ[i][j] = min(righ[i][j], righ[i - 1][j]);
}
int w = righ[i][j] + lef[i][j] - 1;
int h = heigh[i][j];
ans1 = max(ans1, min(w, h) * min(w, h));
ans2 = max(ans2, w * h);
}
}
cout << ans1 << endl;
cout << ans2 << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
read(n, m);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
read(matrix[i][j]);
}
}
solve();
return 0;
}
|