P1169「棋盘制作」

1. 题目

题目链接：P1169「棋盘制作」 。

题目描述

国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个 8×88 \times 8 大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。

而我们的主人公小 Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小 W 决定将棋盘扩大以适应他们的新规则。

小 Q 找到了一张由 N×MN \times M 个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小 Q 想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。

不过小 Q 还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。

于是小 Q 找到了即将参加全国信息学竞赛的你，你能帮助他么？

输入格式

包含两个整数 NN 和 MM，分别表示矩形纸片的长和宽。接下来的 NN 行包含一个 N ×MN \ \times M 的 0101 矩阵，表示这张矩形纸片的颜色（00 表示白色，11 表示黑色）。

输出格式

包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。

输入输出样例

输入 #1

1
2
3
4
3 3
1 0 1
0 1 0
1 0 0

输出 #1

1
2
4
6

说明/提示

对于 20%20\% 的数据，N,M≤80N, M ≤ 80 。

对于 40%40\% 的数据，N,M≤400N, M ≤ 400 。

对于 100%100\% 的数据，N,M≤2000N, M ≤ 2000 。

2. 题解

分析

单调栈（方法一）

网上大佬一眼就看出棋盘中的黑白块所在行列编号是且仅是以下两种情况之一：

  • 黑块所在行列数奇偶性相同，白块不同 。
  • 白块所在行列数奇偶性相同，黑块不同 。

于是我们可以对整个棋盘扫描两次，第一次假设符合要求的棋盘为第一种情况，则：

  • 对符合第一种情况的黑白块块标记为 1 。
  • 对不符合第一种情况的黑白块块标记为 0 。
    于是得到第一种情况下满足要求的棋盘最大内矩形/正方形面积则就是二维标记数组对应的矩形的最大内矩形/正方形面积。转化为跟 P4147「玉蟾宫」 基本一样的问题，单调栈轻松解决。

第二次假设符合要求的棋盘为第二种情况，则：

  • 对符合第二种情况的黑白块块标记为 1 。
  • 对不符合第二种情况的黑白块块标记为 0 。
    于是得到第二种情况下满足要求的棋盘最大内矩形/正方形面积则就是二维标记数组对应的矩形的最大内矩形/正方形面积。转化为跟 P4147「玉蟾宫」 基本一样的问题，单调栈轻松解决。

最终答案即是满足上述两种情况之一的棋盘最大内矩形/正方形的最大值。

单调栈（方法二）

对于蒟蒻的我，没有大佬们那样的洞察力。我的想法是这样的：类似 P4147「玉蟾宫」 一样，对整个棋盘 a[i][j],i∈[0,n),j∈[0,m)a[i][j],i \in [0,n), j \in [0,m) 进行逐行扫描，记录点 (i,j)(i,j) 对应的最大满足要求的列高 b[i][j]b[i][j]，即从点 (i,j)(i,j) 向上连续的黑白块交替的块长度：

∀j∈[0,m), b[0][j]=1∀i∈[1,n), b[i][j]={1if  b[i][j]=b[i−1][j]b[i−1][j]+1if  b[i][j]≠b[i−1][j]\begin{array}{c} \forall j \in [0,m), \ b[0][j] = 1 \\ \forall i \in [1,n), \ b[i][j] = \begin{cases} 1 & if \ \ b[i][j] = b[i-1][j] \\ b[i-1][j] + 1 & if \ \ b[i][j] \ne b[i-1][j] \\ \end{cases} \end{array}

然后同样利用单调栈的思想，对每行分别处理。不同的是，处理点 (i,j)(i,j) 时：

  • 如果 a[i][j−1]≠a[i][j] a[i][j-1] \ne a[i][j] 时，说明对于第 ii 行来说，列 jj 满足以列 j−1j-1 结尾形成的棋盘要求，此时按照普通的单调栈将 b[i][j]b[i][j] 压栈即可。

  • 如果 a[i][j−1]=a[i][j] a[i][j-1] = a[i][j] 时，说明对于第 ii 行来说，列 jj 不满足以列 j−1j-1 结尾形成的棋盘要求，此时棋盘已经割裂，即 jj 以后的所有列都无法与 jj 前面的列组合成合理的棋盘，于是将栈弹空，并修改栈顶的矩形边界为 j−1j-1 后，再将 b[i][j]b[i][j] 压栈。

整体还是单调栈的思想，只是压栈操作做了一些修改。

悬线法

这道题也可以用悬线法来解决。悬线法主要涉及到三个数组：

  • height[i][j]height[i][j] ：用来表示点 (i,j)(i,j) 向上可达到的最高高度 。
  • left[i][j]left[i][j] ：用来表示点 (i,j)(i,j) 向左可延伸到的最大左边界。
  • right[i][j]right[i][j] ：用来表示点 (i,j)(i,j) 向右可延伸到的最小右边界。

悬线法首先需要初始化这三个数组：

height[i][j]=1left[i][j]=right[i][j]=1\begin{array}{c} height[i][j] = 1 \\ left[i][j] = right[i][j] = 1 \end{array}

然后按行处理每一个点在该行可达到的最大左边界 left[i][j]left[i][j] 和最小右边界：

left[i][j]=left[i][j−1],如果点(i,j)和点(i,j−1)之前没有障碍点right[i][j]=right[i][j+1],如果点(i,j)和点(i,j+1)之间没有障碍点\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)(i,j) 向上可到达的最高高度，同时更新以该高度为高的最大内矩形的最大左边界和最小右边界：

height[i][j]=h[i−1][j]+1,如果点(i,j)和点(i−1,j)之间没有障碍点left[i][j]=max⁡(left[i][j],left[i−1][j])right[i][j]=min⁡(right[i][j],right[i−1][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)(i,j) 向上（优先级最高）向左向右（优先级次之）能够形成的最大矩形面积，并记录满足条件的答案即可。

代码

单调栈（方法一）

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
90
91
92
93
94
95
96
97
98
99
100
#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;
}

单调栈（方法二）

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
#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;
}

悬线法

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
#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;
}
Technique ACM 题解
Technique ACM 题解

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！