[CERC2016] 外观分析 Appearance Analysis

题意

整张图片由很多大小完全相同的窗口组成，窗口之间和最外层边框都用一格 # 隔开。

每个窗口内部只会出现 . 和 +，表示这个窗口的图案。

如果两个窗口的图案在旋转 0 / 90 / 180 / 270 度后能够完全重合，就认为它们是同一种图案；不允许翻转。

要求统计整张图片里一共有多少种本质不同的窗口图案。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
101#include <bits/stdc++.h>
using namespace std;

int r, c;
vector<string> grid_data;
vector<int> border_rows, border_cols;

vector<string> rotate90(const vector<string> &mat) {
    int h = (int)mat.size();
    int w = (int)mat[0].size();
    vector<string> res(w, string(h, '.'));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            res[j][h - 1 - i] = mat[i][j];
        }
    }
    return res;
}

// 直接判断两个窗口是否能通过旋转匹配。
bool same_pattern(vector<string> a, const vector<string> &b) {
    if ((int)a.size() == (int)b.size() && (int)a[0].size() == (int)b[0].size() && a == b) {
        return true;
    }
    for (int t = 1; t <= 3; t++) {
        a = rotate90(a);
        if ((int)a.size() == (int)b.size() && (int)a[0].size() == (int)b[0].size() && a == b) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> r >> c;
    grid_data.resize(r);
    for (int i = 0; i < r; i++) {
        cin >> grid_data[i];
    }

    for (int i = 0; i < r; i++) {
        bool all_hash = true;
        for (int j = 0; j < c; j++) {
            if (grid_data[i][j] != '#') {
                all_hash = false;
                break;
            }
        }
        if (all_hash) {
            border_rows.push_back(i);
        }
    }
    for (int j = 0; j < c; j++) {
        bool all_hash = true;
        for (int i = 0; i < r; i++) {
            if (grid_data[i][j] != '#') {
                all_hash = false;
                break;
            }
        }
        if (all_hash) {
            border_cols.push_back(j);
        }
    }

    int win_h = border_rows[1] - border_rows[0] - 1;
    int win_w = border_cols[1] - border_cols[0] - 1;
    int row_cnt = (int)border_rows.size() - 1;
    int col_cnt = (int)border_cols.size() - 1;

    // brute.cpp：把所有窗口都拆出来，逐个和已有代表图案比较，直接判断旋转等价。
    vector<vector<string>> kinds;
    for (int i = 0; i < row_cnt; i++) {
        for (int j = 0; j < col_cnt; j++) {
            int sr = border_rows[i] + 1;
            int sc = border_cols[j] + 1;
            vector<string> mat(win_h);
            for (int x = 0; x < win_h; x++) {
                mat[x] = grid_data[sr + x].substr(sc, win_w);
            }

            bool found = false;
            for (int id = 0; id < (int)kinds.size(); id++) {
                if (same_pattern(mat, kinds[id])) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                kinds.push_back(mat);
            }
        }
    }

    cout << kinds.size() << '\n';

    return 0;
}

这题本身不难，关键是把窗口先正确切出来。

由于窗口之间的边框整行、整列都是 #，而窗口内部只会出现 . 和 +，所以：

一整行全是 # 的行，一定是横向边框
一整列全是 # 的列，一定是纵向边框

找出所有这样的边框行和边框列后，相邻两条边框之间夹着的区域就是一个窗口。
所有窗口大小相同，因此第一个间隔就能确定窗口高和宽。

把每个窗口内容提取出来后，问题就变成：

如何判断两个窗口在旋转意义下是否等价？

做法是给每个窗口求一个“规范表示”：

记录原图案
再考虑旋转后的图案
在所有允许的旋转结果里，取字典序最小的编码字符串作为代表

这里有一个细节：

如果窗口不是正方形，旋转 90 度和 270 度后长宽会交换，不能和原尺寸窗口匹配
所以非正方形窗口只需要比较 0 度和 180 度
正方形窗口才需要比较四种旋转

最后把每个窗口的规范表示丢进 set，集合大小就是答案。

代码

cpp

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117#include <bits/stdc++.h>
using namespace std;

int r, c;
vector<string> grid_data;
vector<int> border_rows, border_cols;

// 把一个窗口图案编码成字符串，方便放进 set 去重。
string encode_pattern(const vector<string> &mat) {
    string res = "";
    int h = (int)mat.size();
    int w = (int)mat[0].size();
    res += to_string(h);
    res += "x";
    res += to_string(w);
    res += "|";
    for (int i = 0; i < h; i++) {
        res += mat[i];
        res += "/";
    }
    return res;
}

// 顺时针旋转 90 度。
vector<string> rotate90(const vector<string> &mat) {
    int h = (int)mat.size();
    int w = (int)mat[0].size();
    vector<string> res(w, string(h, '.'));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            res[j][h - 1 - i] = mat[i][j];
        }
    }
    return res;
}

// 取一个窗口在允许旋转下的最小表示。
string canonical(const vector<string> &mat) {
    vector<string> cur = mat;
    string best = encode_pattern(cur);

    // 180 度旋转总是和原窗口同尺寸，因此一定要考虑。
    cur = rotate90(cur);
    if ((int)mat.size() == (int)mat[0].size()) {
        best = min(best, encode_pattern(cur));
    }

    cur = rotate90(cur);
    best = min(best, encode_pattern(cur));

    cur = rotate90(cur);
    if ((int)mat.size() == (int)mat[0].size()) {
        best = min(best, encode_pattern(cur));
    }

    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> r >> c;
    grid_data.resize(r);
    for (int i = 0; i < r; i++) {
        cin >> grid_data[i];
    }

    for (int i = 0; i < r; i++) {
        bool all_hash = true;
        for (int j = 0; j < c; j++) {
            if (grid_data[i][j] != '#') {
                all_hash = false;
                break;
            }
        }
        if (all_hash) {
            border_rows.push_back(i);
        }
    }

    for (int j = 0; j < c; j++) {
        bool all_hash = true;
        for (int i = 0; i < r; i++) {
            if (grid_data[i][j] != '#') {
                all_hash = false;
                break;
            }
        }
        if (all_hash) {
            border_cols.push_back(j);
        }
    }

    int win_h = border_rows[1] - border_rows[0] - 1;
    int win_w = border_cols[1] - border_cols[0] - 1;
    int row_cnt = (int)border_rows.size() - 1;
    int col_cnt = (int)border_cols.size() - 1;

    set<string> kinds;

    for (int i = 0; i < row_cnt; i++) {
        for (int j = 0; j < col_cnt; j++) {
            int sr = border_rows[i] + 1;
            int sc = border_cols[j] + 1;
            vector<string> mat(win_h);
            for (int x = 0; x < win_h; x++) {
                mat[x] = grid_data[sr + x].substr(sc, win_w);
            }
            kinds.insert(canonical(mat));
        }
    }

    cout << kinds.size() << '\n';

    return 0;
}

复杂度

设整张图大小为 r × c。

扫描边框行和边框列： $O(rc)$
提取所有窗口并生成规范表示：总共仍然只会访问每个格子常数次，所以是 $O(rc)$

总时间复杂度 $O(rc)$ ，空间复杂度 $O(rc)$ 。

总结

这题核心就是两步：

利用整行整列的 # 把窗口切出来
用旋转后的最小表示做去重

本质上是一道非常直接的网格模拟题。

[CERC2016] 外观分析 Appearance Analysis

目录

题意

思路

代码

复杂度

总结