HDU 4121
43796 ワード
http://www.bnuoj.com/v3/problem_show.php？pid=10277
1 //#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
2 #include <stdio.h>
3 #include <iostream>
4 #include <climits>
5 #include <cstring>
6 #include <cmath>
7 #include <stack>
8 #include <vector>
9 #include <algorithm>
10 #define ll long long
11 using namespace std;
12
13 const int INF = 0x3f3f3f3f;
14 const int MAXN = 1001;
15 const int row = 10;
16 const int col = 9;
17
18 int map[20][20];
19 int G_x, G_y, pos_x, pos_y;
20 bool ans;
21
22 bool deal(int x, int y){
23 return (x >= 1 && x <= row && y >= 1 && y <= col);
24 }
25
26 bool deal_plus(int x, int y){
27 if(deal(x, y) && x <= 3 && y >= 4 && y <= 6) return true;
28 return false;
29 }
30
31 void init(){
32 ans = false;
33 memset(map, 0, sizeof(map));
34 }
35
36 bool shuai(int x, int y){
37 int i, j;
38 if(x - 1 < pos_x) return false;
39 for(i = x - 1; i >= pos_x; --i){
40 if(map[i][y]) break;
41 }
42 if(map[i][y] == 5) return true;
43 return false;
44 }
45
46 bool ju(int x, int y){
47 int i, j;
48 for(i = x + 1; i <= pos_x; ++i){
49 if(x + 1 > pos_x) break;
50 if(map[i][y]){
51 if(map[i][y] == 5) return true;
52 else break;
53 }
54 }
55 for(i = x - 1; i >= 1; --i){
56 if(x - 1 < 1) break;
57 if(map[i][y]){
58 if(map[i][y] == 5) return true;
59 else break;
60 }
61 }
62 for(j = y - 1; j >= 1; --j){
63 if(y - 1 < 1) break;
64 if(map[x][j]){
65 if(map[x][j] == 5) return true;
66 else break;
67 }
68 }
69 for(j = y + 1; j <= col; ++j){
70 if(y + 1 > col) break;
71 if(map[x][j]){
72 if(map[x][j] == 5) return true;
73 else break;
74 }
75 }
76 return false;
77 }
78
79 bool pao(int x, int y){
80 bool flag = false;
81 int i, j;
82 for(i = x + 1; i <= pos_x; ++i){
83 if(x + 1 > pos_x) break;
84 if(flag){
85 if(map[i][y] == 5 ) return true;
86 else break;
87 } else if(map[i][y]){
88 flag = true;
89 }
90 }
91 flag = false;
92 for(i = x - 1; i >= 1; --i){
93 if(x - 1 < 1) break;
94 if(flag){
95 if(map[i][y] == 5) return true;
96 else break;
97 } else if(map[i][y]){
98 flag = true;
99 }
100 }
101 flag = false;
102 for(j = y - 1; j >= 1; --j){
103 if(y - 1 < 1) break;
104 if(flag){
105 if(map[x][j] == 5) return true;
106 else break;
107 } else if(map[x][j]){
108 flag = true;
109 }
110 }
111 flag = false;
112 for(j = y + 1; j <= col; ++j){
113 if(y + 1 > col) break;
114 if(flag){
115 if(map[x][j] == 5) return true;
116 else break;
117 } else if(map[x][j]){
118 flag = true;
119 }
120 }
121 return false;
122 }
123
124 bool ma(int x, int y){
125 int xx, yy;
126
127 xx = x + 2; yy = y - 1;
128 if(xx == pos_x && yy == pos_y && map[x + 1][y] == 0) return true;
129
130 xx = x + 2; yy = y + 1;
131 if(xx == pos_x && yy == pos_y && map[x + 1][y] == 0) return true;
132
133 xx = x + 1; yy = y + 2;
134 if(xx == pos_x && yy == pos_y && map[x][y + 1] == 0) return true;
135
136 xx = x - 1; yy = y + 2;
137 if(xx == pos_x && yy == pos_y && map[x][y + 1] == 0) return true;
138
139 xx = x - 2; yy = y + 1;
140 if(xx == pos_x && yy == pos_y && map[x - 1][y] == 0) return true;
141
142 xx = x - 2; yy = y - 1;
143 if(xx == pos_x && yy == pos_y && map[x - 1][y] == 0) return true;
144
145 xx = x - 1; yy = y - 2;
146 if(xx == pos_x && yy == pos_y && map[x][y - 1] == 0) return true;
147
148 xx = x + 1; yy = y - 2;
149 if(xx == pos_x && yy == pos_y && map[x][y - 1] == 0) return true;
150
151 return false;
152 }
153
154 bool beat(int x, int y){
155 int i, j;
156 if(x + 1 > row) return false;
157 for(i = x + 1; i <= row; ++i){
158 if(map[i][y]) break;
159 }
160 if(map[i][y] == 1) return true;
161 return false;
162 }
163
164 bool solve(){
165 int i, j;
166 for(i = 1; i <= row; ++i){
167 for(j = 1; j <= col; ++j){
168 if(map[i][j] == 1)
169 if(shuai(i, j)) return true;
170 if(map[i][j] == 2)
171 if(ju(i, j)) return true;
172 if(map[i][j] == 3)
173 if(pao(i, j)) return true;
174 if(map[i][j] == 4)
175 if(ma(i, j)) return true;
176 }
177 }
178 return false;
179 }
180
181 int main(){
182 int i, j, t;
183 char cc;
184 while(cin >> t >> G_x >> G_y){
185 if(t == 0 && G_x == 0 && G_y == 0) break;
186 init();
187 map[G_x][G_y] = 5;
188 while(t--){
189 cin >> cc >> pos_x >> pos_y;
190 if(cc == 'G'){
191 map[pos_x][pos_y] = 1;
192 } else if(cc == 'R'){
193 map[pos_x][pos_y] = 2;
194 } else if(cc == 'C'){
195 map[pos_x][pos_y] = 3;
196 } else if(cc == 'H'){
197 map[pos_x][pos_y] = 4;
198 }
199 }
200 if(beat(G_x, G_y)){
201 ans = false;
202 }
203 else{
204 if(deal_plus(G_x - 1, G_y)){
205 map[G_x][G_y] = 0;
206 int temp_num = map[G_x - 1][G_y];
207 map[G_x - 1][G_y] = 5;
208 pos_x = G_x - 1;
209 pos_y = G_y;
210
211 if(solve()){
212 ans = true;
213 }
214 else{
215 printf("NO
");
216 continue;
217 }
218 map[G_x - 1][G_y] = temp_num;
219 map[G_x][G_y] = 5;
220 }
221 if(deal_plus(G_x + 1, G_y)){
222 map[G_x][G_y] = 0;
223 int temp_num = map[G_x + 1][G_y];
224 map[G_x + 1][G_y] = 5;
225 pos_x = G_x + 1;
226 pos_y = G_y;
227
228 if(solve()){
229 ans = true;
230 }
231 else{
232 printf("NO
");
233 continue;
234 }
235 map[G_x + 1][G_y] = temp_num;
236 map[G_x][G_y] = 5;
237 }
238 if(deal_plus(G_x, G_y - 1)){
239 map[G_x][G_y] = 0;
240 int temp_num = map[G_x][G_y - 1];
241 map[G_x][G_y - 1] = 5;
242 pos_x = G_x;
243 pos_y = G_y - 1;
244
245 if(solve()){
246 ans = true;
247 }
248 else{
249 printf("NO
");
250 continue;
251 }
252 map[G_x][G_y - 1] = temp_num;
253 map[G_x][G_y] = 5;
254 }
255 if(deal_plus(G_x, G_y + 1)){
256 map[G_x][G_y] = 0;
257 int temp_num = map[G_x][G_y + 1];
258 map[G_x][G_y + 1] = 5;
259 pos_x = G_x;
260 pos_y = G_y + 1;
261
262 if(solve()){
263 ans = true;
264 }
265 else{
266 printf("NO
");
267 continue;
268 }
269 map[G_x][G_y + 1] = temp_num;
270 map[G_x][G_y] = 5;
271 }
272 }
273 if(ans){
274 printf("YES
");
275 } else{
276 printf("NO
");
277 }
278 }
279 return 0;
280 }