Posted on 2008-06-21 10:40
superman 阅读(440)
评论(1) 编辑 收藏 引用 所属分类:
POJ
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 struct point { int x, y; } ;
7
8 int n, m, T;
9 char map[20][20];
10
11 bool door[5]; int key[5];
12
13 int x[20][20];
14 void bfs(int sx, int sy)
15 {
16 map[sx][sy] = 'T';
17
18 point sp = { sx, sy };
19
20 queue <point> q;
21 q.push(sp);
22
23 point cp;
24 while(q.empty() == false)
25 {
26 cp = q.front(); q.pop();
27
28 x[cp.x][cp.y] = T;
29
30 if(map[cp.x][cp.y] >= 'A' && map[cp.x][cp.y] <= 'E')
31 continue;
32
33 //up
34 if(cp.x - 1 >= 0 && x[cp.x - 1][cp.y] == 0 && map[cp.x - 1][cp.y] != '|')
35 {
36 point np = { cp.x - 1, cp.y };
37 q.push(np);
38 }
39 //down
40 if(cp.x + 1 < n && x[cp.x + 1][cp.y] == 0 && map[cp.x + 1][cp.y] != '|')
41 {
42 point np = { cp.x + 1, cp.y };
43 q.push(np);
44 }
45 //left
46 if(cp.y - 1 >= 0 && x[cp.x][cp.y - 1] == 0 && map[cp.x][cp.y - 1] != '|')
47 {
48 point np = { cp.x, cp.y - 1};
49 q.push(np);
50 }
51 //right
52 if(cp.y + 1 < m && x[cp.x][cp.y + 1] == 0 && map[cp.x][cp.y + 1] != '|')
53 {
54 point np = { cp.x, cp.y + 1};
55 q.push(np);
56 }
57 }
58 }
59
60 int main()
61 {
62 while(scanf("%d %d", &n, &m) != EOF)
63 {
64 if(n == 0 && m == 0)
65 break;
66
67 memset(x, false, sizeof(x));
68 memset(door, false, sizeof(door));
69 memset(key, 0, sizeof(key));
70
71 int sx, sy, tx, ty;
72
73 sx = sy = tx = ty = -1;
74 for(int i = 0; i < n; i++)
75 for(int j = 0; j < m; j++)
76 {
77 cin >> map[i][j];
78 if(map[i][j] == 'S') sx = i, sy = j;
79 if(map[i][j] == 'G') tx = i, ty = j;
80 if(map[i][j] == 'X') map[i][j] = '|';
81 }
82
83 if(sx == -1 || sy == -1 || tx == -1 || ty == -1)
84 {
85 cout << "NO" << endl; continue;
86 }
87
88 for(int i = 0; i < n; i++)
89 for(int j = 0; j < m; j++)
90 if(map[i][j] >= 'A' && map[i][j] <= 'E')
91 door[map[i][j] - 'A'] = true;
92
93 for(int k = 0; k < 5; k++)
94 if(door[k] == false)
95 for(int i = 0; i < n; i++)
96 for(int j = 0; j < m; j++)
97 if(map[i][j] == char(k + 'a'))
98 map[i][j] = '.';
99
100 for(int i = 0; i < n; i++)
101 for(int j = 0; j < m; j++)
102 if(map[i][j] >= 'a' && map[i][j] <= 'e')
103 key[map[i][j] - 'a']++;
104
105 T = 1;
106 bfs(sx, sy);
107
108 if(x[tx][ty])
109 {
110 cout << "YES" << endl; continue;
111 }
112 int keycnt[5] = { 0 };
113 while(true)
114 {
115 for(int i = 0; i < n; i++)
116 for(int j = 0; j < m; j++)
117 if(x[i][j] == T && map[i][j] >= 'a' && map[i][j] <= 'e')
118 keycnt[map[i][j] - 'a']++;
119
120 T++;
121 bool flag = false;
122 for(int k = 0; k < 5; k++)
123 if(door[k] && key[k] && keycnt[k] == key[k])
124 for(int i = 0; i < n; i++)
125 for(int j = 0; j < m; j++)
126 if(x[i][j] && map[i][j] == char(k + 'A'))
127 {
128 bfs(i, j); door[k] = false; flag = true;
129 }
130
131 if(flag == false)
132 {
133 cout << "NO" << endl; break;
134 }
135 if(x[tx][ty])
136 {
137 cout << "YES" << endl; break;
138 }
139 }
140 }
141
142 return 0;
143 }
144