Contents
Problem
透過給定的圖片，來判斷有出現哪些古文字。
圖片可能會有拉伸變形。
Solution
輸入方式採用 16 進位轉 2 進位。
利用中間的空格來判斷屬於哪張圖，題目中的六張圖剛好分別有 0~5 個空格。
先 DFS 從四個邊開始將背景清掉，也就是不屬於古文字的部分。
開始 DFS 整張圖，由於黑的格子其上下左右必有一個也是黑，就朝四個方向開始進行。
只要掃到白的(背景白已清除)，就先將白的封閉區先走完，並記錄下來。
走完該區域的白，再回來走黑的，直到完成該古文字。最後統計即可。
要注意遞迴的寫法有可能會造成記憶體錯誤，udebug 中有一筆測資就會造成遞迴太深。但 UVa 丟上去仍然會過就是了。
改成用 stack 寫可以解決，但速度不知為何並沒變快，或許是我哪裡出錯了。
Code
遞迴寫法：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
int H, W;
// 上下左右
const int dir_x[4] = {-1, 0, 0, 1};//r
const int dir_y[4] = {0, -1, 1, 0};//c
// 6 個圖形的空格: (A,1), (J,3), (D,5), (S,4), (W,0), (K,2)
const int white_to_type_idx[6] = {5, 0, 3, 2, 4, 1}; //有3個空格: white_to_type_idx[3] = 2 => type[2] = 'J'
const char type[6] = {'A', 'D', 'J', 'K', 'S', 'W'}; // alphabetic order
int image[201][50 * 4 + 1]; // [1][1] 為左上角
bool visit[201][50 * 4 + 1];
int white_count;
bool in_border(int r, int c);
void init_image();
void dfs_init_image(int r, int c);
void dfs_scan_lang(int r, int c);
void dfs_scan_white(int r, int c);
int main()
{
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
char *hex[16] = {
"0000", "0001", "0010", "0011",
"0100", "0101", "0110", "0111",
"1000", "1001", "1010", "1011",
"1100", "1101", "1110", "1111"};
int Case = 0;
while (scanf("%d%d", &H, &W) != EOF && H && W)
{
int i, j, k;
getchar();
char c;
for (i = 1; i <= H; i++)
{
for (j = 1; j <= W; j++)
{
c = getchar();
int num = isalpha(c) ? c - 'a' + 10 : c - '0';
for (k = 0; k < 4; k++)
{
image[i][4 * (j - 1) + k + 1] = (hex[num][k] == '0') ? WHITE : BLACK;
visit[i][4 * (j - 1) + k + 1] = false;
}
}
getchar();
}
//init
W *= 4;
memset(visit, false, sizeof visit);
init_image();
int type_count[6] = {}; // 計算各種類有幾個
/*for (i = 1; i <= H; i++)
{
for (j = 1; j <= W; j++)
printf("%3d", image[i][j]);
putchar('\n');
}*/
for (i = 1; i <= H; i++)
for (j = 1; j <= W; j++)
if (!visit[i][j] && image[i][j] == BLACK)
{
white_count = 0;
dfs_scan_lang(i, j);
type_count[white_to_type_idx[white_count]]++;
}
printf("Case %d: ", ++Case);
for (i = 0; i < 6; i++)
for (j = 0; j < type_count[i]; j++)
putchar(type[i]);
putchar('\n');
}
return 0;
}
inline bool in_border(int r, int c)
{
return (r && c && r <= H && c <= W);
}
void init_image()
{
int i;
// 將與古文字無關的 pixel 標記成 -1, 清掉背景
// 檢查四個邊, 如都沒白的, 代表只有一個古文字
// 有可能該處被黑包圍導致 dfs中斷, 必須檢查四個邊
for (i = 1; i <= W; i++)
{
if (!image[1][i])
dfs_init_image(1, i);
if (!image[H][i])
dfs_init_image(H, i);
}
for (i = 1; i <= H; i++)
{
if (!image[i][1])
dfs_init_image(i, 1);
if (!image[i][W])
dfs_init_image(i, W);
}
}
void dfs_init_image(int r, int c)
{
// (WHITE not in word) -> NONE
image[r][c] = NONE; // 與古文字無關的pixel
visit[r][c] = true;
for (int i = 0; i < 4; i++)
{
int rr = r + dir_x[i], cc = c + dir_y[i];
//printf("%d %d %d %d\n", rr, cc, image[rr][cc], visit[rr][cc]);
if (in_border(rr, cc) && !image[rr][cc])
dfs_init_image(rr, cc);
}
}
void dfs_scan_lang(int r, int c)
{
visit[r][c] = true;
if (image[r][c] == BLACK)
{
for (int i = 0; i < 4; i++)
{
int rr = r + dir_x[i], cc = c + dir_y[i];
if (in_border(rr, cc) && !visit[rr][cc])
dfs_scan_lang(rr, cc);
}
}
else if (image[r][c] == WHITE)
{
white_count++;
for (int i = 0; i < 4; i++)
{
int rr = r + dir_x[i], cc = c + dir_y[i];
if (in_border(rr, cc) && image[rr][cc] == WHITE && !visit[rr][cc])
{
// 遇到白的就先把該封閉區都掃過一次
dfs_scan_white(rr, cc);
/*
for (int i = 1; i <= H; i++)
{
for (int j = 1; j <= W; j++)
printf("%3c", visit[i][j] ? 'X' : 'O');
putchar('\n');
}
*/
}
}
}
}
void dfs_scan_white(int r, int c)
{
visit[r][c] = true;
for (int i = 0; i < 4; i++)
{
int rr = r + dir_x[i], cc = c + dir_y[i];
if (in_border(rr, cc) && image[rr][cc] == WHITE && !visit[rr][cc])
dfs_scan_white(rr, cc);
}
}
用 stack：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
183
184
185
186
187
188
189
190
191
192
193
194
195
using namespace std;
typedef pair<int, int> node;
int H, W;
// 上下左右
const int dir_x[4] = {-1, 0, 0, 1}; //r
const int dir_y[4] = {0, -1, 1, 0}; //c
// 6 個圖形的空格: (A,1), (J,3), (D,5), (S,4), (W,0), (K,2)
const int white_to_type_idx[6] = {5, 0, 3, 2, 4, 1}; //有3個空格: white_to_type_idx[3] = 2 => type[2] = 'J'
const char type[6] = {'A', 'D', 'J', 'K', 'S', 'W'}; // alphabetic order
int image[201][50 * 4 + 1]; // [1][1] 為左上角
bool visit[201][50 * 4 + 1];
int white_count;
bool in_border(int r, int c);
void init_image();
void dfs_init_image(int r, int c);
void dfs_scan_lang(int r, int c);
int main()
{
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
char *hex[16] = {
"0000", "0001", "0010", "0011",
"0100", "0101", "0110", "0111",
"1000", "1001", "1010", "1011",
"1100", "1101", "1110", "1111"};
int Case = 0;
while (scanf("%d%d", &H, &W) != EOF && H && W)
{
int i, j, k;
getchar();
char c;
for (i = 1; i <= H; i++)
{
for (j = 1; j <= W; j++)
{
c = getchar();
int num = isalpha(c) ? c - 'a' + 10 : c - '0';
for (k = 0; k < 4; k++)
{
image[i][4 * (j - 1) + k + 1] = (hex[num][k] == '0') ? WHITE : BLACK;
visit[i][4 * (j - 1) + k + 1] = false;
}
}
getchar();
}
//init
W *= 4;
memset(visit, false, sizeof visit);
init_image();
int type_count[6] = {}; // 計算各種類有幾個
/*for (i = 1; i <= H; i++)
{
for (j = 1; j <= W; j++)
printf("%3d", image[i][j]);
putchar('\n');
}*/
for (i = 1; i <= H; i++)
for (j = 1; j <= W; j++)
if (!visit[i][j] && image[i][j] == BLACK)
{
white_count = 0;
dfs_scan_lang(i, j);
type_count[white_to_type_idx[white_count]]++;
}
printf("Case %d: ", ++Case);
for (i = 0; i < 6; i++)
for (j = 0; j < type_count[i]; j++)
putchar(type[i]);
putchar('\n');
}
return 0;
}
inline bool in_border(int r, int c)
{
return (r && c && r <= H && c <= W);
}
void init_image()
{
int i;
// 將與古文字無關的 pixel 標記成 -1, 清掉背景
// 檢查四個邊, 如都沒白的, 代表只有一個古文字
// 有可能該處被黑包圍導致 dfs中斷, 必須檢查四個邊
for (i = 1; i <= W; i++)
{
if (!image[1][i])
dfs_init_image(1, i);
if (!image[H][i])
dfs_init_image(H, i);
}
for (i = 1; i <= H; i++)
{
if (!image[i][1])
dfs_init_image(i, 1);
if (!image[i][W])
dfs_init_image(i, W);
}
}
void dfs_init_image(int r, int c)
{
stack<node> s;
s.push(make_pair(r, c));
while (!s.empty())
{
node next = s.top();
s.pop();
r = next.first;
c = next.second;
if (visit[r][c])
continue;
// (WHITE not in word) -> NONE
image[r][c] = NONE; // 與古文字無關的pixel
visit[r][c] = true;
for (int i = 0; i < 4; i++)
{
int rr = r + dir_x[i], cc = c + dir_y[i];
if (in_border(rr, cc) && !image[rr][cc])
s.push(std::make_pair(rr, cc));
}
}
}
void dfs_scan_lang(int r, int c)
{
bool white_flag = true;
stack<node> s;
s.push(make_pair(r, c));
while (!s.empty())
{
node next = s.top();
s.pop();
r = next.first;
c = next.second;
if (visit[r][c])
continue;
visit[r][c] = true;
if (image[r][c] == BLACK)
{
if (!white_flag)
white_flag = true;
for (int i = 0; i < 4; i++)
{
int rr = r + dir_x[i], cc = c + dir_y[i];
if (in_border(rr, cc) && !visit[rr][cc])
s.push(std::make_pair(rr, cc));
}
}
else if (image[r][c] == WHITE)
{
if (white_flag)
{
white_count++;
white_flag = false;
}
for (int i = 0; i < 4; i++)
{
// 遇到白的就先把該封閉區都掃過一次
int rr = r + dir_x[i], cc = c + dir_y[i];
if (in_border(rr, cc) && image[rr][cc] == WHITE && !visit[rr][cc])
s.push(std::make_pair(rr, cc));
}
}
}
}
改得簡潔一點：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
using std::pair;
using std::stack;
typedef pair<int, int> node;
int H, W;
// 上下左右
const int dir_x[4] = {-1, 0, 0, 1}; //r
const int dir_y[4] = {0, -1, 1, 0}; //c
// 6 個圖形的空格: (A,1), (J,3), (D,5), (S,4), (W,0), (K,2)
const int white_to_type_idx[6] = {5, 0, 3, 2, 4, 1}; //有3個空格: white_to_type_idx[3] = 2 => type[2] = 'J'
const char type[6] = {'A', 'D', 'J', 'K', 'S', 'W'}; // alphabetic order
int image[201][50 * 4 + 1]; // [1][1] 為左上角
bool visit[201][50 * 4 + 1];
int white_count;
bool in_border(int r, int c);
void dfs(int r, int c, int color);
void init_image();
int main()
{
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
int Case = 0;
while (scanf("%d%d", &H, &W) != EOF && H && W)
{
int i, j, k;
getchar();
char c;
for (i = 1; i <= H; i++)
{
for (j = 1; j <= W; j++)
{
c = getchar();
int num = isalpha(c) ? c - 'a' + 10 : c - '0';
for (k = 0; k < 4; k++)
{
image[i][4 * (j - 1) + 3 - k + 1] = ((1 << k) & num) ? 1 : 0;
visit[i][4 * (j - 1) + 3 - k + 1] = false;
}
}
getchar();
}
//init
W *= 4;
memset(visit, false, sizeof visit);
init_image();
int type_count[6] = {}; // 計算各種類有幾個
/*for (i = 1; i <= H; i++)
{
for (j = 1; j <= W; j++)
printf("%3d", image[i][j]);
putchar('\n');
}*/
for (i = 1; i <= H; i++)
for (j = 1; j <= W; j++)
if (!visit[i][j] && image[i][j] == BLACK)
{
white_count = 0;
dfs(i, j, BLACK);
type_count[white_to_type_idx[white_count]]++;
}
printf("Case %d: ", ++Case);
for (i = 0; i < 6; i++)
for (j = 0; j < type_count[i]; j++)
putchar(type[i]);
putchar('\n');
}
return 0;
}
inline bool in_border(int r, int c)
{
return (r && c && r <= H && c <= W);
}
void dfs(int r, int c, int color)
{
stack<node> s;
s.push(std::make_pair(r, c));
while (!s.empty())
{
node next = s.top();
s.pop();
r = next.first;
c = next.second;
if (visit[r][c])
continue;
if (image[r][c] == WHITE && color == BLACK)
{
dfs(r, c, WHITE);
white_count++;
continue;
}
else if (image[r][c] != color)
continue;
visit[r][c] = true;
for (int i = 0; i < 4; i++)
{
int rr = r + dir_x[i], cc = c + dir_y[i];
if (in_border(rr, cc) && !visit[rr][cc])
s.push(std::make_pair(rr, cc));
}
}
}
void init_image()
{
// 將與古文字無關的 pixel 標記成拜訪過, 清掉背景
// 檢查四個邊, 如都沒白的, 代表只有一個古文字
// 有可能該處被黑包圍導致 dfs 中斷, 必須檢查四個邊
for (int i = 1; i <= W; i++)
{
if (!image[1][i] && !visit[1][i])
dfs(1, i, WHITE);
if (!image[H][i] && !visit[H][i])
dfs(H, i, WHITE);
}
for (int i = 1; i <= H; i++)
{
if (!image[i][1] && !visit[i][1])
dfs(i, 1, WHITE);
if (!image[i][W] && !visit[i][W])
dfs(i, W, WHITE);
}
}