UVA 1103

这里主要是探讨对书里面的实现的理解。

题面

书上给出的中文的题面如下，

原本的英文的题面可以在 vjudge 中找到，

https://vjudge.net/problem/UVA-1103

书中的分析是这个样子，

实现

这个问题的第一个关键是识别题目的意思，关于这个其实书上面已经给出来了，那就是黑色的符号里面有多少个白洞，即，我们识别这个符号，只需要识别 1 连通块中有多少个 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
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
// fany
// Ankh => A: 1
// Wedjat => J: 3
// Djed => D: 5
// Scarab => S: 4
// Was => W: 0
// Akhet => K: 2
#define _CRT_SECURE_NO_WARNINGS
// UVa1103 Ancient Messages
// Rujia Liu
// we pad one empty line/column to the top/bottom/left/right border, so color 1 is always "background" white

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

char bin[256][5];

const int maxh = 200 + 5;
const int maxw = 50 * 4 + 5;

int H, W, pic[maxh][maxw], color[maxh][maxw];

char line[maxw];

void decode(char ch, int row, int col) {
    for (int i = 0; i < 4; i++) pic[row][col + i] = bin[ch][i] - '0';
}

// => 左、右、上、下
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

// dfs from (row, col) and paint color c

void dfs(int row, int col, int c) {
    color[row][col] = c;           // 这里是对色块的 color 进行染色的操作
    for (int i = 0; i < 4; i++) {  // 左、右、上、下
        int row2 = row + dr[i];
        int col2 = col + dc[i];
        // 四个条件
        // 1、行满足边界条件
        // 2、列满足边界条件
        // 3、当前方向的 pic 值要与原来的相同
        // 4、当前搜索正在处理的色块的 color 要为 0，也就是说，没有被染过色，也就是说，没有被之前的 dfs 处理过
        if (row2 >= 0 && row2 < H && col2 >= 0 && col2 < W && pic[row2][col2] == pic[row][col] && color[row2][col2] == 0) dfs(row2, col2, c);  // 在递归进去的时候，不会对 cnt 进行修改
    }
}

vector<set<int>> neighbors;

void check_neighbors(int row, int col) {
    // 左、右、上、下
    for (int i = 0; i < 4; i++) {
        int row2 = row + dr[i];
        int col2 = col + dc[i];
        // 四个条件
        // 1、行满足边界条件
        // 2、列满足边界条件
        // 3、当前方向的 pic 值要与原来的相同
        // 4、当前方向的色块的 color 要不为 1，也就是说，不为最外面的大的 0 连通块
        if (row2 >= 0 && row2 < H && col2 >= 0 && col2 < W && pic[row2][col2] == 0 && color[row2][col2] != 1) neighbors[color[row][col]].insert(color[row2][col2]);
    }
}

const char* code = "WAKJSD";

char recognize(int c) {
    int cnt = neighbors[c].size();  // 这个值就是里面的空洞的数量
    return code[cnt];
}

// use this function to print the decoded picture
void print() {
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) printf("%d", pic[i][j]);
        printf("\n");
    }
}

int main() {
    // 重定向到文件
    freopen("./UVa1103.txt", "r", stdin);

    strcpy(bin['0'], "0000");
    strcpy(bin['1'], "0001");
    strcpy(bin['2'], "0010");
    strcpy(bin['3'], "0011");
    strcpy(bin['4'], "0100");
    strcpy(bin['5'], "0101");
    strcpy(bin['6'], "0110");
    strcpy(bin['7'], "0111");
    strcpy(bin['8'], "1000");
    strcpy(bin['9'], "1001");
    strcpy(bin['a'], "1010");
    strcpy(bin['b'], "1011");
    strcpy(bin['c'], "1100");
    strcpy(bin['d'], "1101");
    strcpy(bin['e'], "1110");
    strcpy(bin['f'], "1111");

    int kase = 0;

    while (scanf("%d%d", &H, &W) == 2 && H) {
        memset(pic, 0, sizeof(pic));
        for (int i = 0; i < H; i++) {
            scanf("%s", line);
            for (int j = 0; j < W; j++) decode(line[j], i + 1, j * 4 + 1);
        }

        H += 2;
        W = W * 4 + 2;
        int cnt = 0;
        vector<int> cc;                   // connected components of 1
        memset(color, 0, sizeof(color));  // color 一开始都是为 0 的
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                if (!color[i][j]) {                         // 如果 color 没有被染过色，即，之前没有被搜索遍历过
                    dfs(i, j, ++cnt);                       // cnt 会在这里变化
                    if (pic[i][j] == 1) cc.push_back(cnt);  // 如果颜色是 1，那么，这个连通块就是一个符号形状的边界
                }

        // 打印 cc vector
        std::cout << "================cc vector================" << '\n';
        for (auto n : cc) {
            std::cout << n << ' ';
        }
        std::cout << '\n';
        std::cout << "=============cc vector ends==============" << '\n';

        neighbors.clear();  // 清空

        neighbors.resize(cnt + 1);  // 扩展到 cnt + 1 这个尺寸
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                if (pic[i][j] == 1) check_neighbors(i, j);  // pic 的值为 1，注意，不是 color => check_neighbors

        vector<char> ans;
        for (int i = 0; i < cc.size(); i++) ans.push_back(recognize(cc[i]));
        sort(ans.begin(), ans.end());
        printf("Case %d: ", ++kase);
        for (int i = 0; i < ans.size(); i++) printf("%c", ans[i]);
        printf("\n");

        // 打印 pic 数组
        std::cout << "================pic array================" << '\n';
        for (int row = 0; row < H; row++) {
            for (int col = 0; col < W; col++) {
                std::cout << pic[row][col] << ' ';
            }
            std::cout << '\n';
        }
        std::cout << "=============pic array ends==============" << '\n';

        // 打印 color 数组
        std::cout << "================color array================" << '\n';
        for (int row = 0; row < H; row++) {
            for (int col = 0; col < W; col++) {
                std::cout << color[row][col] << ' ';
            }
            std::cout << '\n';
        }
        std::cout << "=============color array ends==============" << '\n';

        // 打印 neighbors vector
        std::cout << "================neighbors vector================" << '\n';
        for (auto set : neighbors) {
            for (auto n : set) {
                std::cout << n << ' ';
            }
            std::cout << '\n';
        }
        std::cout << "=============neighbors vector ends==============" << '\n';
    }

    return 0;
}

这里，我简单地把输入进行了重定向，然后，我使用的数据是，

1
2
3
4
5
6
7
8
9
10
11
10 3
000
778
548
748
578
700
000
7f0
1e0
000

程序执行的结果如下，

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
================cc vector================
2 3 7
=============cc vector ends==============
Case 1: AKW
================pic array================
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 1 1 1 1 0 0 0 0
0 0 1 0 1 0 1 0 0 1 0 0 0 0
0 0 1 1 1 0 1 0 0 1 0 0 0 0
0 0 1 0 1 0 1 1 1 1 0 0 0 0
0 0 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
=============pic array ends==============
================color array================
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 2 2 2 1 3 3 3 3 1 1 1 1
1 1 2 4 2 1 3 5 5 3 1 1 1 1
1 1 2 2 2 1 3 5 5 3 1 1 1 1
1 1 2 6 2 1 3 3 3 3 1 1 1 1
1 1 2 2 2 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 7 7 7 7 7 7 7 1 1 1 1 1
1 1 1 1 7 7 7 7 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
=============color array ends==============
================neighbors vector================


4 6
5




=============neighbors vector ends==============

结合实际打印出来的结果，理解起来应该会更加容易。

题外话

期待我的友人可以尽快地理解完这本书的全部内容，然后我也可以从他的理解中吸收一点必要的养分。有人可以一起探讨是一件不错的事情。

算法 UVA

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