题目链接:P1169「棋盘制作」 。
国际象棋是世界上最古老的博弈游戏之一,和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想,棋盘是一个8 \times 8大小的黑白相间的方阵,对应八八六十四卦,黑白对应阴阳。
而我们的主人公小 Q,正是国际象棋的狂热爱好者。作为一个顶尖高手,他已不满足于普通的棋盘与规则,于是他跟他的好朋友小 W 决定将棋盘扩大以适应他们的新规则。
小 Q 找到了一张由 N \times M 个正方形的格子组成的矩形纸片,每个格子被涂有黑白两种颜色之一。小 Q 想在这种纸中裁减一部分作为新棋盘,当然,他希望这个棋盘尽可能的大。
不过小 Q 还没有决定是找一个正方形的棋盘还是一个矩形的棋盘(当然,不管哪种,棋盘必须都黑白相间,即相邻的格子不同色),所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积,从而决定哪个更好一些。
于是小 Q 找到了即将参加全国信息学竞赛的你,你能帮助他么?
包含两个整数 N 和 M,分别表示矩形纸片的长和宽。接下来的 N 行包含一个 N \ \times M 的 01 矩阵,表示这张矩形纸片的颜色(0 表示白色,1表示黑色)。
包含两行,每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积,第二行为可以找到的最大矩形棋盘的面积(注意正方形和矩形是可以相交或者包含的)。
3 3
1 0 1
0 1 0
1 0 0
4
6
对于 20\% 的数据,N, M ≤ 80 。
对于 40\% 的数据,N, M ≤ 400 。
对于 100\% 的数据,N, M ≤ 2000 。
网上大佬一眼就看出棋盘中的黑白块所在行列编号是且仅是以下两种情况之一:
于是我们可以对整个棋盘扫描两次,第一次假设符合要求的棋盘为第一种情况,则:
第二次假设符合要求的棋盘为第二种情况,则:
最终答案即是满足上述两种情况之一的棋盘最大内矩形/正方形的最大值。
对于蒟蒻的我,没有大佬们那样的洞察力。我的想法是这样的:类似 P4147「玉蟾宫」 一样,对整个棋盘 a[i][j],i \in [0,n), j \in [0,m) 进行逐行扫描,记录点(i,j) 对应的最大满足要求的列高 b[i][j],即从点(i,j) 向上连续的黑白块交替的块长度:
然后同样利用单调栈的思想,对每行分别处理。不同的是,处理点 (i,j) 时:
整体还是单调栈的思想,只是压栈操作做了一些修改。
这道题也可以用悬线法来解决。悬线法主要涉及到三个数组:
悬线法首先需要初始化这三个数组:
\begin{array}{c} height[i][j] = 1 \\ left[i][j] = right[i][j] = 1 \end{array}
然后按行处理每一个点在该行可达到的最大左边界left[i][j] 和最小右边界:
\begin{array}{c} left[i][j] = left[i][j-1], \quad \text{如果点} (i,j) \text{和点} (i,j-1) \text{之前没有障碍点} \\ right[i][j] = right[i][j+1], \quad \text{如果点} (i,j) \text{和点} (i,j+1) \text{之间没有障碍点} \end{array}
接着按列处理点 (i,j)向上可到达的最高高度,同时更新以该高度为高的最大内矩形的最大左边界和最小右边界:
\begin{array}{c} height[i][j] = h[i-1][j] + 1, \quad \text{如果点} (i,j) \text{和点} (i-1,j) \text{之间没有障碍点} \\ left[i][j] = \max (left[i][j], left[i-1][j]) \\ right[i][j] = \min (right[i][j], right[i-1][j]) \end{array}
最后,计算以点(i,j) 向上(优先级最高)向左向右(优先级次之)能够形成的最大矩形面积,并记录满足条件的答案即可。
#include <bits/stdc++.h>
#define MAXN 2005
using namespace std;
int ans1 = 0;
int ans2 = 0;
struct DC{
int i;
int v;
DC(): i(0),v(0) {}
DC(int _i, int _v): i(_i),v(_v) {}
};
void maxRectangle(int *b, int m) {
DC dc[MAXN];
int depth = 0;
dc[depth] = DC{-1,-1};
for(int j = 0; j < m; ++j) {
int sdepth = depth;
while(depth && b[j] <= dc[depth].v) {
int c = dc[sdepth].i - dc[depth-1].i;
int d = dc[depth].v;
ans1 = max(ans1, min(c*c, d*d));
ans2 = max(ans2, c*d);
--depth;
}
dc[++depth] = DC{j,b[j]};
}
int sdepth = depth;
while(depth) {
int c = dc[sdepth].i - dc[depth-1].i;
int d = dc[depth].v;
ans1 = max(ans1, min(c*c, d*d));
ans2 = max(ans2, c*d);
--depth;
}
}
int main()
{
int n, m;
static int a[MAXN][MAXN], b[MAXN][MAXN], c[MAXN][MAXN];
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
scanf("%d", &a[i][j]);
}
}
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if((!((i&1)^(j&1)) && a[i][j]) || (((i&1)^(j&1)) && !a[i][j])){
b[i][j] = 1;
} else {
b[i][j] = 0;
}
}
}
for(int j = 0; j < m; ++j) {
c[0][j] = b[0][j];
}
for(int i = 1; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(b[i][j]) {
c[i][j] = c[i-1][j] + 1;
} else {
c[i][j] = 0;
}
}
}
for(int i = 0; i < n; ++i) {
maxRectangle(c[i], m);
}
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if((!((i&1)^(j&1)) && a[i][j]) || (((i&1)^(j&1)) && !a[i][j])){
b[i][j] = 0;
} else {
b[i][j] = 1;
}
}
}
for(int j = 0; j < m; ++j) {
c[0][j] = b[0][j];
}
for(int i = 1; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(b[i][j]) {
c[i][j] = c[i-1][j] + 1;
} else {
c[i][j] = 0;
}
}
}
for(int i = 0; i < n; ++i) {
maxRectangle(c[i], m);
}
printf("%d\n%d\n", ans1, ans2);
return 0;
}
#include <bits/stdc++.h>
#define MAXN 2005
using namespace std;
int ans1 = 0;
int ans2 = 0;
struct DC{
int i;
int v;
DC(): i(0),v(0) {}
DC(int _i, int _v): i(_i),v(_v) {}
};
void maxRectangle(int a[], int b[], int m) {
int depth = 0;
DC stack[MAXN];
stack[depth] = DC{-1,-1};
stack[++depth] = DC{0,b[0]};
for(int j = 1; j < m; ++j) {
int sdepth = depth;
if(a[j-1] != a[j]) {
while(depth && stack[depth].v >= b[j]) {
int c = stack[sdepth].i - stack[depth-1].i;
int d = stack[depth].v;
ans1 = max(ans1, min(c*c, d*d));
ans2 = max(ans2, c*d);
--depth;
}
} else {
while(depth) {
int c = stack[sdepth].i - stack[depth-1].i;
int d = stack[depth].v;
ans1 = max(ans1, min(c*c, d*d));
ans2 = max(ans2, c*d);
--depth;
}
stack[0].i = j - 1;
}
stack[++depth] = DC{j,b[j]};
}
int sdepth = depth;
while(depth) {
int c = stack[sdepth].i - stack[depth-1].i;
int d = stack[depth].v;
ans1 = max(ans1, min(c*c, d*d));
ans2 = max(ans2, c*d);
--depth;
}
}
int main()
{
int n, m;
static int a[MAXN][MAXN], b[MAXN][MAXN];
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
scanf("%d", &a[i][j]);
}
}
for(int j = 0; j < m; ++j) {
b[0][j] = 1;
}
for(int i = 1; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(a[i][j] != a[i-1][j]) {
b[i][j] = b[i-1][j] + 1;
} else {
b[i][j] = 1;
}
}
}
for(int i = 0; i < n; ++i) {
maxRectangle(a[i], b[i], m);
}
printf("%d\n%d\n", ans1, ans2);
return 0;
}
#include <bits/stdc++.h>
#define MAXN 2005
using namespace std;
int main()
{
int n, m;
static int a[MAXN][MAXN], l[MAXN][MAXN], r[MAXN][MAXN], h[MAXN][MAXN];
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
scanf("%d", &a[i][j]);
}
}
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
l[i][j] = j;
r[i][j] = j;
h[i][j] = 1;
}
}
// 处理每一行
for(int i = 0; i < n; ++i) {
for(int j = 1; j < m; ++j) {
if(a[i][j] != a[i][j-1]) {
l[i][j] = l[i][j-1];
}
}
for(int j = m-2; ~j; --j) {
if(a[i][j] != a[i][j+1]) {
r[i][j] = r[i][j+1];
}
}
}
// 处理每一列
for(int i = 1; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(a[i][j] != a[i-1][j]) {
h[i][j] = h[i-1][j] + 1;
l[i][j] = max(l[i][j], l[i-1][j]);
r[i][j] = min(r[i][j], r[i-1][j]);
}
}
}
int ans1 = 0;
int ans2 = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
int c = r[i][j] - l[i][j] + 1;
int d = h[i][j];
ans1 = max(ans1, min(c*c, d*d));
ans2 = max(ans2, c*d);
}
}
printf("%d\n%d\n", ans1, ans2);
return 0;
}