分析:
- 可以知道的是,給定的 slash Maze 中只存在 ‘/’ 和 ‘\’ ,將斜線或反斜線離散化為 3 * 3 單位的方格,比如
用數字 1 表示單位被覆蓋,數字 0 表示單位是空白,則 /
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
也可以用 2 * 2 的單元格表示圖像,但是需要特判,而這種方法不需要特判,而且相對容易實現
-
對圖像的邊界使用 Flood Fill 染色為數字 2,因為邊界部分不可能構成環(想一想),排除不構成環的部分
-
第 2 步以后,對 slash Maze 數字為 0 的空格使用 dfs 找出最大的環長度,也可以使用 flood fill 直接找出
1 /*
2 PROG: Slash Maze
3 ID : yewei
4 LANG: C++
5 */
6 #pragma warnning (disable : 4786)
7
8 #include <memory.h>
9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13
14 using namespace std;
15
16 const int MAXN = 229;
17 const int dx[] = {-1, 1, 0, 0};
18 const int dy[] = {0, 0, -1, 1};
19
20 int w, h, cycles, grids, maxGrids, cas = 1;
21 int graph[MAXN][MAXN];
22 bool vis[MAXN][MAXN], hash[MAXN][MAXN];
23
24 void debug() {
25 for (int i = 0; i < h; ++i) {
26 for (int j = 0; j < w; ++j) {
27 if (graph[i][j] == 1) {
28 printf("*");
29 } else if (graph[i][j] == 2) {
30 printf("#");
31 } else if (graph[i][j] == 0) {
32 printf(" ");
33 }
34 }
35 printf("\n");
36 }
37 printf("\n");
38 }
39
40 void readGraph() {
41 char ch;
42
43 h *= 3, w *= 3;
44 for (int i = 1; i < h; i += 3) {
45 getchar();
46 for (int j = 1; j < w; j += 3) {
47 scanf("%c", &ch);
48 if (ch == '\\') {
49 graph[i][j] = 1;
50 graph[i - 1][j - 1] = graph[i + 1][j + 1] = 1;
51 graph[i - 1][j] = graph[i + 1][j] = 0;
52 graph[i][j - 1] = graph[i][j + 1] = 0;
53 graph[i - 1][j + 1] = graph[i + 1][j - 1] = 0;
54 } else if (ch == '/') {
55 graph[i][j] = 1;
56 graph[i - 1][j + 1] = graph[i + 1][j - 1] = 1;
57 graph[i - 1][j] = graph[i + 1][j] = 0;
58 graph[i][j - 1] = graph[i][j + 1] = 0;
59 graph[i - 1][j - 1] = graph[i + 1][j + 1] = 0;
60 }
61 }
62 }
63 // debug();
64 }
65
66 bool isBoundary(int &x, int &y) {
67 return (x == 0 || y == 0 || x == h - 1 || y == w - 1);
68 }
69
70 bool isOut(int &x, int &y) {
71 return (x < 0 || y < 0 || x >= h || y >= w);
72 }
73
74 void flood_fill(int x, int y, int color) {
75 vis[x][y] = true;
76 graph[x][y] = color;
77 for (int i = 0; i < 4; ++i) {
78 int nx = x + dx[i];
79 int ny = y + dy[i];
80 if (!isOut(nx, ny) && !vis[nx][ny] && !graph[nx][ny]) {
81 flood_fill(nx, ny, color);
82 }
83 }
84 }
85
86 void colorBoundary() {
87 for (int i = 0; i < h; ++i) {
88 for (int j = 0; j < w; ++j) {
89 if (isBoundary(i, j) && !vis[i][j] && !graph[i][j]) {
90 flood_fill(i, j, 2);
91 }
92 }
93 }
94 // debug();
95 }
96
97 void dfs(int x, int y) {
98 ++grids;
99 hash[x][y] = true;
100 for (int i = 0; i < 4; ++i) {
101 int nx = x + dx[i];
102 int ny = y + dy[i];
103 if (!isOut(nx, ny) && !graph[nx][ny] && !hash[nx][ny]) {
104 dfs(nx, ny);
105 }
106 }
107 }
108
109 void solve() {
110 cycles = 0, maxGrids = -1;
111 for (int i = 0; i < h; ++i) {
112 for (int j = 0; j < w; ++j) {
113 if (!graph[i][j] && !hash[i][j]) {
114 ++cycles;
115 grids = 0;
116 dfs(i, j);
117 if (grids > maxGrids) {
118 maxGrids = grids;
119 }
120 }
121 }
122 }
123 }
124
125 void solve();
126
127 int main() {
128 while (~scanf("%d %d", &w, &h) && w + h != 0) {
129 memset(vis, false, sizeof(vis));
130 memset(hash, false, sizeof(hash));
131 memset(graph, -1, sizeof(graph));
132
133 readGraph();
134 colorBoundary();
135 solve();
136
137 printf("Maze #%d:\n", cas++);
138 if (cycles) {
139 printf("%d Cycles; the longest has length %d.\n", cycles, maxGrids / 3);
140 } else {
141 printf("There are no cycles.\n");
142 }
143 printf("\n");
144 }// End of while
145
146 return 0;
147 }
148 /*
149 # Problem Verdict Language Run Time Submission Date
150 10592483 705 Slash Maze Accepted C++ 0.036 2012-09-12 03:01:16
151 */
原文链接: https://www.cnblogs.com/yewei/archive/2012/09/12/2681600.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/62637
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!