這題沒把我弄瘋了.一個小時寫完,改了2個小時...題目給的數據太弱了,需要自己寫一些數據來驗證...在這里給大家提供些數據
題目
Maze
| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 1205 |
|
Accepted: 399 |
Description
Acm, a treasure-explorer, is exploring again. This time he is in a special maze, in which there are some doors (at most 5 doors, represented by 'A', 'B', 'C', 'D', 'E' respectively). In order to find the treasure, Acm may need to open doors. However, to open a door he needs to find all the door's keys (at least one) in the maze first. For example, if there are 3 keys of Door A, to open the door he should find all the 3 keys first (that's three 'a's which denote the keys of 'A' in the maze). Now make a program to tell Acm whether he can find the treasure or not. Notice that Acm can only go up, down, left and right in the maze.
Input
The input consists of multiple test cases. The first line of each test case contains two integers M and N (1 < N, M < 20), which denote the size of the maze. The next M lines give the maze layout, with each line containing N characters. A character is one of the following: 'X' (a block of wall, which the explorer cannot enter), '.' (an empty block), 'S' (the start point of Acm), 'G' (the position of treasure), 'A', 'B', 'C', 'D', 'E' (the doors), 'a', 'b', 'c', 'd', 'e' (the keys of the doors). The input is terminated with two 0's. This test case should not be processed.
Output
For each test case, in one line output "YES" if Acm can find the treasure, or "NO" otherwise.
Sample Input
4 4
S.X.
a.X.
..XG
....
3 4
S.Xa
.aXB
b.AG
0 0
Sample Output
YES
NO
數據:
5 5
S....
XXAXa
GX..X
.X...
.....
20 20
S..................a
aXXXXXXXXXXAXXXXXXX.
.X........bb......X.
.XbXXXXXXXXXXXXXX.X.
.X.X.....c......X.X.
aXbX.XXXXXXXXXX.X.X.
.X.X.X........X.X.X.
.X.X.X.XDXXXX.X.X.X.
.X.X.X.X..XXX.X.X.X.
.X.X.X.X.XG.X.X.X.X.
.X.XcX.X.XXEX.CeX.X.
.X.X.X.X.e..X.X.X.X.
.X.X.X.XXXXXX.X.X.X.
.X.X.X........X.X.X.
.X.X.XXXXXXXXXX.X.X.
.X.X..c.........X.X.
.X.XXXXXXXBXXXXXX.X.
.X........b.......X.
.XXXXXXXXXXXXXXXXXX.
.d..e...a........a..
主要思想,先找鑰匙..搜索一遍,得到能找到的鑰匙,然后開門.把能開的門都打開..打開門之后再找鑰匙,然后在開門.
直到找到G..
代碼如下:
Source Code
| Problem: 2157 |
|
User: luoguangyao |
| Memory: 276K |
|
Time: 0MS |
| Language: C++ |
|
Result: Accepted |
- Source Code
1
#include <iostream>
2
3using namespace std;
4
5int m;
6int n;
7char map[22][22];
8
int allkey[6] = 
{0};
9int key[6] = {0};
10int mark[22][22] = {0};
11int mark2[22][22] = {0};
12int markkey[22][22] = {0};
13int lock = 1;
14int kk = 0;
15
16void FindKey(int x,int y)
17{
18
if ((map[x][y] >= 'a'&& map[x][y] <= 'e')
19 && markkey[x][y] != 1)
20
{
21 key[map[x][y] - 'a']++;
22
23 markkey[x][y] = 1;
24
}
25
26 mark2[x][y] = 1;
27
28 if (mark2[x + 1][y] != 1 && x + 1 < m && map[x + 1][y] != 'X' && map[x + 1][y] != 'A' && map[x + 1][y] != 'B'
29 && map[x + 1][y] != 'C' && map[x + 1][y] != 'D' && map[x + 1][y] != 'E')
30 {
31 FindKey(x + 1 , y);
32 }
33
34 if (mark2[x - 1][y] != 1 && x - 1 >= 0 && map[x - 1][y] != 'X' && map[x - 1][y] != 'A' && map[x - 1][y] != 'B'
35 && map[x - 1][y] != 'C' && map[x - 1][y] != 'D' && map[x - 1][y] != 'E')
36 {
37 FindKey(x - 1 , y);
38 }
39
40 if (mark2[x][y + 1] != 1 && y + 1 < n && map[x][y + 1] != 'X' && map[x][y + 1] != 'A' && map[x][y + 1] != 'B'
41 && map[x][y + 1] != 'C' && map[x][y + 1] != 'D' && map[x][y + 1] != 'E' )
42 {
43 FindKey(x , y + 1);
44 }
45
46 if (mark2[x][y - 1] != 1 && y - 1 >= 0 && map[x][y - 1] != 'X' && map[x][y - 1] != 'A' && map[x][y - 1] != 'B'
47 && map[x][y - 1] != 'C' && map[x][y - 1] != 'D' && map[x][y - 1] != 'E')
48 {
49 FindKey(x , y - 1);
50 }
51
}
52
53void Findroute(int x,int y)
54{
55 if (map[x][y] == 'G')
56 {
57 lock = 0;
58 }
59
60 FindKey(x , y);
61
62 mark[x][y] = 1;
63
64 if (mark[x + 1][y] != 1 && x + 1 < m && map[x + 1][y] != 'X')
65 {
66 if (map[x + 1][y] >= 'A' && map[x + 1][y] <= 'E')
67 {
68 if (key[map[x + 1][y] - 'A'] != 0 && allkey[map[x + 1][y] - 'A'] == key[map[x + 1][y] - 'A'])
69 {
70 Findroute(x + 1 , y);
71 }
72 }
73 else
74 {
75 Findroute(x + 1 , y);
76 }
77 }
78
79 if (mark[x - 1][y] != 1 && x - 1 >= 0 && map[x - 1][y] != 'X')
80 {
81 if (map[x - 1][y] >= 'A' && map[x - 1][y] <= 'E')
82 {
83 if (key[map[x - 1][y] - 'A'] != 0 && key[map[x - 1][y] - 'A'] == allkey[map[x - 1][y] - 'A'])
84 {
85 Findroute(x - 1 , y);
86 }
87 }
88 else
89 {
90 Findroute(x - 1 , y);
91 }
92 }
93
94 if (mark[x][y - 1] != 1 && y - 1 >= 0 && map[x][y - 1] != 'X')
95 {
96 if (map[x][y - 1] >= 'A' && map[x][y - 1] <= 'E')
97 {
98 if (key[map[x][y - 1] - 'A'] != 0 && allkey[map[x][y - 1] - 'A'] == key[map[x][y - 1] - 'A'])
99 {
100 Findroute(x , y - 1);
101 }
102 }
103 else
104 {
105 Findroute(x , y - 1);
106 }
107 }
108
109 if (mark[x][y + 1] != 1 && y + 1 < n && map[x][y + 1] != 'X')
110 {
111 if (map[x][y + 1] >= 'A' && map[x][y + 1] <= 'E')
112 {
113 if (key[map[x][y + 1] - 'A'] != 0 && allkey[map[x][y + 1] - 'A'] == key[map[x][y + 1] - 'A'])
114 {
115 Findroute(x , y + 1);
116 }
117 }
118 else
119 {
120 Findroute(x , y + 1);
121 }
122 }
123
124}
125
126int main()
127{
128 int i;
129 int j;
130
131 while (cin >> m >> n)
132 {
133 int px = -1;
134 int py = -1;
135 int gx = -1;
136 int gy = -1;
137
138 memset(key,0,sizeof(key));
139 memset(allkey,0,sizeof(allkey));
140 memset(map,'\0',sizeof(map));
141 memset(mark,0,sizeof(mark));
142 memset(mark2,0,sizeof(mark2));
143 memset(markkey,0,sizeof(markkey));
144 lock = 1;
145
146 if (m == 0 && n == 0)
147 {
148 break;
149 }
150
151 for (i = 0; i < m ; ++i)
152 {
153 for (j = 0; j < n; ++j)
154 {
155 cin >> map[i][j];
156
157 if (map[i][j] >= 'a' && map[i][j] <= 'e')
158 {
159 allkey[map[i][j] - 'a']++;
160 }
161
162 if (map[i][j] == 'S')
163 {
164 px = i;
165 py = j;
166 }
167
168 if (map[i][j] == 'G')
169 {
170 gx = i;
171 gy = j;
172 }
173 }
174 }
175
176 if (px == -1 || py == -1 || gx == -1 || gy == -1)
177 {
178 cout << "NO" << endl;
179 continue;
180 }
181
182 Findroute(px,py);
183
184 if (lock == 1)
185 {
186 cout << "NO" << endl;
187 }
188 else
189 {
190 cout << "YES" << endl;
191 }
192 }
193
194 return 0;
195}
196
posted on 2009-03-07 15:14
生活要低調 閱讀(1259)
評論(0) 編輯 收藏 引用