1 //
2 // http://en.wikipedia.org/wiki/F%C5%ABrinkazan
3 //
4 import util;
5 import game;
6
7 interface Solver
8 {
9 // this(in Game g);
10 char single_step();
11 void force(char c);
12 }
13
14
15 bool is_spacy(char c)
16 {
17 return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O';
18 }
19
20 bool is_rocky(char c)
21 {
22 return c=='*' || c=='@';
23 }
24
25 bool is_true_space(char c)
26 {
27 return c==' ';
28 }
29
30 bool is_trampoline_source(char c)
31 {
32 return 'A'<=c && c<='I';
33 }
34
35 bool is_rocklambda(char c)
36 {
37 return is_rocky(c) || c=='\\';
38 }
39
40 Tuple!(string,int) death_move(in Game g)
41 {
42 // TODO: S
43
44 string death;
45 int breath;
46 int y = g.map.robot.y;
47 int x = g.map.robot.x;
48 int[5] dy_=[+1,-1,0,0,0];
49 int[5] dx_=[0,0,-1,+1,0];
50 char[] ds=['U','D','L','R','W'];
51 for(int i=0; i<5; ++i)
52 {
53 bool after_move_death(int y, int x, char tr_tgt)
54 {
55 bool is_spacy_t(char c) {
56 if(is_true_space(c) || c=='R' || c==tr_tgt)
57 return true;
58 return ('A'<=c && c<='I' && g.tr.target_of(c)==tr_tgt);
59 }
60
61 // check water
62 if( g.map[y,x]!='O' && g.hp==0 && y<=g.water_level )
63 return true;
64
65 // check falling rock.
66 int yy=y+1, xx=x;
67 if( is_spacy_t(g.map[yy, xx]) )
68 {
69 if( is_rocky(g.map[yy+1,xx]) )
70 return true;
71 if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx+1]) && is_rocky(g.map[yy,xx+1]) ) {
72 if( is_spacy_t(g.map[yy+1,xx+2]) && is_spacy_t(g.map[yy,xx+2]) )
73 return false;
74 return true;
75 }
76 if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx-1]) && is_rocklambda(g.map[yy,xx-1]) ) {
77 if(g.hige_until_rise == 1 && g.map[yy+1,xx+1]=='W')
78 return false;
79 return true;
80 }
81 }
82 return false;
83 }
84
85 int dy=dy_[i], dx=dx_[i];
86 if( is_spacy(g.map[y+dy,x+dx]) || dy==0 && is_rocky(g.map[y,x+dx]) && is_true_space(g.map[y,x+2*dx]) )
87 {
88 if( after_move_death(y+dy, x+dx, char.init) )
89 death ~= ds[i];
90 else if(ds[i] != 'W')
91 breath ++;
92 }
93 else if( is_trampoline_source(g.map[y+dy,x+dx]) )
94 {
95 Pos p = g.tr.target_pos(g.map[y+dy,x+dx]);
96 if( after_move_death(p.y, p.x, g.tr.target_of(g.map[y+dy,x+dx])) )
97 death ~= ds[i];
98 else
99 breath ++;
100 }
101 else
102 {
103 death ~= ds[i];
104 }
105 }
106
107 return tuple(death, breath);
108 }
109
110 class Queue(T)
111 {
112 alias Tuple!(T,int) t;
113
114 t[] cur, next;
115
116 void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); }
117 bool empty() { return cur.empty; }
118 t pop() {
119 t v = cur[0]; cur = cur[1..$];
120 if(cur.empty) { cur = next; next = null; }
121 return v;
122 }
123 }
124
125 ///
126 /// Solver "Mountain": be immovable like a mountain.
127 ///
128 class 不動如山 : Solver
129 {
130 this(in Game g) {}
131 char single_step() { return 'W'; }
132 void force(char c) {}
133 }
134
135 ///
136 /// Solver "Forest": shows contemplation.
137 ///
138 class 徐如林 : Solver
139 {
140 int wait_count = 0;
141 int choke_count = 0;
142
143 Game g;
144 this(in Game g)
145 {
146 this.g = g.clone();
147 forbidden_cell = new bool[][](g.map.H+2, g.map.W+2);
148 }
149
150 char single_step()
151 {
152 Tuple!(string,int) de = death_move(g);
153 char c = act(g, de[0], de[1]);
154 force(c);
155 return c;
156 }
157
158 void force(char c)
159 {
160 if(c != 'A')
161 g.command(c);
162 }
163
164 Tuple!(Pos, int)[] log;
165 bool[][] forbidden_cell;
166
167 char act(const(Game) g, string death, int breath)
168 {
169 const Pos ro = g.map.robot;
170 const Pos li = g.map.lift;
171 Pos[] la = g.map.lambdas();
172 sort!((Pos a,Pos b){
173 int ad=abs(a.y-li.y)+abs(a.x-li.x);
174 int bd=abs(b.y-li.y)+abs(b.x-li.x);
175 return ad>bd;;
176 })(la);
177 Pos[] ra = g.map.razors();
178 const(Pos)[] hi = g.map.objects('W');
179
180 Tuple!(char,int)[] cand;
181 char c = 'W';
182 if( g.map.collected_lambda == g.map.total_lambda ) {
183 cand = search(g, ro, [li], death);
184 } else if( !la.empty ){
185 cand ~= search(g, ro, la~ra, death);
186 }
187
188 // 'higesori' mode
189 if( !hi.empty && g.map.razor>0 ) {
190 int his = 0;
191 for(int dy=-1; dy<=+1; ++dy)
192 for(int dx=-1; dx<=+1; ++dx)
193 if(g.map[ro.y+dy,ro.x+dx] == 'W')
194 his++;
195
196 if(his>=2 || his==hi.length)
197 cand = [tuple('S',int.max)];
198 if(cand.empty) {
199 const(Pos)[] tgt;
200 for(int y=1; y<=g.map.H; ++y)
201 for(int x=1; x<=g.map.W; ++x)
202 if(g.map[y,x]=='.'||g.map[y,x]==' ') {
203 his = 0;
204 for(int dy=-1; dy<=+1; ++dy)
205 for(int dx=-1; dx<=+1; ++dx)
206 if(g.map[y+dy,x+dx] == 'W')
207 his++;
208 if(his>=2)
209 tgt ~= new Pos(y,x);
210 }
211 cand ~= search(g, ro, tgt, death, true);
212 }
213 }
214
215 // 'horo-push' mode
216 if(cand.empty) {
217 Pos[] horo = g.map.objects('@');
218 Pos[] tgt;
219 foreach(p; horo)
220 if((g.map[p.y,p.x-1]==' '||g.map[p.y,p.x-1]=='R')&&
221 (g.map[p.y,p.x+1]==' '||g.map[p.y,p.x+1]=='R')
222 ||(g.map[p.y-1,p.x]==' '||g.map[p.y-1,p.x]=='R'))
223 tgt ~= p;
224
225 for(int y=1; y<=g.map.H; ++y)
226 for(int x=1; x<=g.map.W; ++x)
227 if(g.map[y,x]=='.')
228 if(is_rocky(g.map[y+1,x])||is_rocky(g.map[y+1,x-1])||is_rocky(g.map[y+1,x+1])
229 ||is_rocky(g.map[y,x+1])||is_rocky(g.map[y,x-1]))
230 tgt ~= new Pos(y,x);
231
232 if(!tgt.empty)
233 cand ~= search(g, ro, tgt, death, true);
234 }
235
236 // 'dig' mode
237 if(cand.empty) {
238 Pos[] tgt;
239 for(int y=1; y<=g.map.H; ++y)
240 for(int x=1; x<=g.map.W; ++x)
241 if(g.map[y,x]=='.')
242 if(is_rocky(g.map[y+1,x])||is_rocky(g.map[y+1,x-1])||is_rocky(g.map[y+1,x+1])
243 ||is_rocky(g.map[y,x+1])||is_rocky(g.map[y,x-1]))
244 tgt ~= new Pos(y,x);
245 cand ~= search(g, ro, tgt, death, true);
246 }
247
248 if(cand.empty) {
249 choke_count++;
250 cand ~= tuple('W',int.max);
251 }
252 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
253 if(c1[1] != c2[1])
254 return c1[1] < c2[1];
255 return c1[0] < c2[0];
256 })(cand);
257 c = cand[0][0];
258
259 if(death.count(c) || wait_count>=2) {
260 foreach(char live; "UDLRW")
261 if(death.count(live)==0) {
262 c=live;
263 break;
264 }
265 }
266
267 if(c == 'W')
268 wait_count++;
269 else
270 wait_count = 0;
271 if(wait_count==2)
272 c = 'A';
273 if(choke_count >= g.map.H)
274 c = 'A';
275
276 bool[char] choice;
277 foreach(t; cand)
278 choice[t[0]] = true;
279 log ~= tuple(ro.clone(), cast(int)choice.length);
280 if(log.length > 5)
281 log = log[$-5..$];
282 int cnt = 0;
283 foreach(l; log)
284 if(l[0] == log[$-1][0])
285 ++cnt;
286 if( cnt >= 3 && breath==1 ) {
287 forbidden_cell[ro.y][ro.x] = true;
288 }
289
290 return c;
291 }
292
293 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death, bool danger_ok=false)
294 {
295 bool danger(int y, int x)
296 {
297 if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
298 return false;
299 if(is_rocky(g.map[y+1,x]))
300 return true;
301 if(is_rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||is_rocky(g.map[y,x-1]))
302 && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
303 return true;
304 if(is_rocky(g.map[y+1,x+1]) && is_rocky(g.map[y,x+1]) && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
305 return true;
306 if(is_rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||is_rocky(g.map[y-1,x-1]))
307 && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
308 return true;
309 if(is_rocky(g.map[y,x+1]) && is_rocky(g.map[y-1,x+1]) && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
310 return true;
311 return false;
312 }
313
314 // avoid directly below '*'
315 Tuple!(char,int)[] tryA() {
316 const(Pos)[] q;
317 foreach(p; gs)
318 if(!danger(p.y,p.x))
319 q ~= p;
320 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
321 foreach(p; q) v[p.y][p.x]=true;
322 bool first_step = true;
323 for(int step=1; q.length; ++step) {
324 Pos[] q2;
325 foreach(p; q) {
326 int[] yyy=[p.y-1,p.y,p.y,p.y+1];
327 int[] xxx=[p.x,p.x-1,p.x+1,p.x];
328 string sss="URLD";
329 for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
330 int y = yyy[i];
331 int x = xxx[i];
332 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
333 foreach(ppp; g.tr.source_pos(g.map[y,x])) {
334 yyy ~= ppp.y;
335 xxx ~= ppp.x;
336 }
337 continue;
338 }
339 if(v[y][x]) continue;
340 if(y==s.y && x==s.x && i<4) {
341 char c = sss[i];
342 if( death.count(c) == 0 )
343 return [tuple(c,step)];
344 } else if(forbidden_cell[y][x]){
345 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
346 if(danger(y,x))
347 continue;
348 q2 ~= new Pos(y,x);
349 v[y][x]=true;
350 }
351 }
352 }
353 first_step = false;
354 q = q2;
355 }
356 return [];
357 }
358
359 // any empty space is my ground
360 Tuple!(char,int)[] tryB() {
361 const(Pos)[] q;
362 foreach(p; gs) q ~= p;
363 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
364 foreach(p; q) v[p.y][p.x]=true;
365 bool first_step = true;
366 for(int step=8; q.length; ++step) {
367 Pos[] q2;
368 foreach(p; q) {
369 int[] yyy=[p.y-1,p.y,p.y,p.y+1];
370 int[] xxx=[p.x,p.x-1,p.x+1,p.x];
371 string sss="URLD";
372 for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
373 int y = yyy[i];
374 int x = xxx[i];
375 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
376 foreach(ppp; g.tr.source_pos(g.map[y,x])) {
377 yyy ~= ppp.y;
378 xxx ~= ppp.x;
379 }
380 continue;
381 }
382 if(v[y][x]) continue;
383 if(y==s.y && x==s.x && i<4) {
384 char c = sss[i];
385 if( death.count(c) == 0 )
386 return [tuple(c,step)];
387 } else if(forbidden_cell[y][x]){
388 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
389 q2 ~= new Pos(y,x);
390 v[y][x]=true;
391 }
392 }
393 }
394 first_step = false;
395 q = q2;
396 }
397 return [];
398 }
399
400 // push rocks!
401 Tuple!(char,int)[] tryC() {
402 const(Pos)[] q;
403 foreach(p; gs) q ~= p;
404 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
405 foreach(p; q) v[p.y][p.x]=true;
406 bool first_step = true;
407 for(int step=20; q.length; ++step) {
408 Pos[] q2;
409 foreach(p; q) {
410 int[] yyy=[p.y-1,p.y,p.y,p.y+1];
411 int[] xxx=[p.x,p.x-1,p.x+1,p.x];
412 string sss="URLD";
413 for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
414 int y = yyy[i];
415 int x = xxx[i];
416 if(is_rocky(g.map[p])) {
417 if(i>=4)continue;
418 if(y!=p.y)continue;
419 if(g.map[y,p.x+(p.x-x)]!=' '&&g.map[y,p.x+(p.x-x)]!='R')continue;
420 }
421 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
422 foreach(ppp; g.tr.source_pos(g.map[y,x])) {
423 yyy ~= ppp.y;
424 xxx ~= ppp.x;
425 }
426 continue;
427 }
428 if(v[y][x]) continue;
429 if(y==s.y && x==s.x && i<4) {
430 char c = sss[i];
431 if( death.count(c) == 0 )
432 return [tuple(c,step)];
433 } else if(forbidden_cell[y][x]){
434 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||is_rocky(g.map[y,x])||g.map[y,x]=='!'||i>=4) {
435 q2 ~= new Pos(y,x);
436 v[y][x]=true;
437 }
438 }
439 }
440 first_step = false;
441 q = q2;
442 }
443 return [];
444 }
445 return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
446 }
447 }
448
449 ///
450 /// Solver "Fire": in raiding and plundering other solvers, be like fire.
451 ///
452 class 侵掠如火(SubSolver) : Solver
453 {
454 // Parameters.
455 int PredictFuture = 10;
456 const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL steps
457 const ReplanLength = 400; // O(PF*RCP*RL*SubSolver.single_step)
458
459 Game current_game;
460 SubSolver sub_solver;
461
462 enum {Tentative, Tentative_Stuck, Fixed};
463 string plan;
464 int plan_state;
465 int replan_limit;
466 bool lambda_getter;
467 int clear_improvement = 3;
468
469 this(in Game g)
470 {
471 current_game = g.clone();
472 plan = "";
473 plan_state = Tentative;
474 if(g.map.W*g.map.H <= 400) {
475 RandomChoicePattern = ["UU","UD","UL","UR",
476 "DU","DD","DL","DR",
477 "LU","LD","LL","LR",
478 "RU","RD","RL","RR","UUU","UUUU","UUUUU"];
479 PredictFuture = 20;
480 clear_improvement = 1;
481 }
482 else if(g.map.W*g.map.H <= 4096) {
483 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"];
484 PredictFuture = 10;
485 clear_improvement = 0;
486 }
487 else {
488 RandomChoicePattern = ["U","D","L","R"];
489 PredictFuture = 10;
490 clear_improvement = 0;
491 }
492
493 replan_limit = PredictFuture;
494 }
495
496 char single_step()
497 {
498 if(current_game.dead || current_game.cleared)
499 return 'A';
500
501 // Make enough prediction.
502 while( plan_state==Tentative && plan.length<replan_limit )
503 single_step_predict();
504
505 // If the future is bad, correct.
506 if( plan_state==Tentative_Stuck && plan.length<replan_limit && !lambda_getter )
507 replan();
508
509 // Follow the predicted plan.
510 if( plan.empty )
511 return 'A';
512 char c = plan[0];
513 plan = plan[1..$];
514 int b_lambda = current_game.map.collected_lambda;
515 current_game.command(c);
516 int a_lambda = current_game.map.collected_lambda;
517 if(b_lambda < a_lambda) lambda_getter = false;
518 return c;
519 }
520
521 void force(char c)
522 {
523 if(plan.length>0 && plan[0]==c)
524 {
525 // If matching the plan, just go forward.
526 plan = plan[1..$];
527 }
528 else
529 {
530 // Discard the plan, otherwise.
531 plan_state = Tentative;
532 plan = "";
533 sub_solver = null;
534 }
535 current_game.command(c);
536 }
537
538 void single_step_predict()
539 {
540 if(sub_solver is null) {
541 sub_solver = new SubSolver(current_game);
542 plan = "";
543 }
544
545 char c = sub_solver.single_step();
546 if(c == 'A')
547 plan_state = Tentative_Stuck;
548 else {
549 plan ~= c;
550 if(sub_solver.g.cleared) {
551 if(clear_improvement-->0) {
552 plan_state = Tentative_Stuck;
553 replan_limit = min(plan.length-plan.length/(clear_improvement+1), PredictFuture);
554 } else {
555 plan_state = Fixed;
556 }
557 } else {
558 plan_state = (sub_solver.g.dead ? Tentative_Stuck : Tentative);
559 }
560 }
561 }
562
563 void replan()
564 {
565 // Try to replace every step of the plan by another move.
566 Game g = current_game.clone();
567 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck);
568 int insertion_point = plan.length;
569 bool tiebreak_by_turn = false;
570 int consider_length = min(ReplanLength, g.map.W*g.map.H);
571 if(cand[0].g.cleared) consider_length = min(consider_length, cand[1].length);
572
573 for(int i=0; i<plan.length; ++i) {
574 foreach(string prefix; RandomChoicePattern)
575 if(prefix[0] != plan[i]) {
576 Tuple!(SubSolver, string, int) r = try_plan(g, prefix, consider_length-i-prefix.length);
577 r[1] = plan[0..i] ~ prefix ~ r[1];
578 bool better = false, tbt=false;
579 if(!cand[0].g.cleared && r[0].g.cleared)
580 better = true;
581 else if(cand[0].g.cleared && r[0].g.cleared) {
582 better = cand[0].g.score < r[0].g.score;
583 }
584 else if(!cand[0].g.cleared && !r[0].g.cleared) {
585 if(cand[0].g.map.collected_lambda < r[0].g.map.collected_lambda)
586 better = true;
587 else if(cand[0].g.map.collected_lambda == r[0].g.map.collected_lambda) {
588 if(cand[0].g.dead && !r[0].g.dead)
589 better = true;
590 else if(cand[0].g.dead == r[0].g.dead) {
591 better = (cand[1].length < r[1].length && r[2]!=Tentative_Stuck);
592 tbt = true;
593 }
594 }
595 }
596 if(better) {
597 cand = r;
598 tiebreak_by_turn = true;
599 insertion_point = i+prefix.length;
600 if(r[0].g.cleared) consider_length = min(consider_length, r[1].length);
601 }
602 }
603 g.command(plan[i]);
604 }
605
606 if(cand[2]==Fixed && insertion_point!=plan.length && clear_improvement-->0) {
607 sub_solver = cand[0];
608 plan = cand[1];
609 plan_state = Tentative_Stuck;
610 replan_limit = min(plan.length - insertion_point, PredictFuture);
611 lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
612 } else {
613 sub_solver = cand[0];
614 plan = cand[1];
615 plan_state = (plan.length < PredictFuture ? Fixed : cand[2]);
616 replan_limit = tiebreak_by_turn ? min(PredictFuture, (plan.length+1)/2) : PredictFuture;
617 lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
618 }
619 }
620
621 Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix, int consider_length)
622 {
623 if(consider_length<=0) consider_length = 2;
624
625 SubSolver s = new SubSolver(g);
626 foreach(char c; prefix)
627 s.force(c);
628 string log;
629 int state = Tentative;
630 while(!s.g.cleared && !s.g.dead && log.length<=consider_length) {
631 char c = s.single_step();
632 if( c == 'A' ) {
633 state = Tentative_Stuck;
634 break;
635 }
636 log ~= c;
637 }
638 if(s.g.cleared) state = Fixed;
639 else if(s.g.dead) state = Tentative_Stuck;
640 return tuple(s, log, state);
641 }
642 }
643
644 ///
645 /// Solver "Wind": let your rapidity be that of the wind.
646 ///
647 class 疾如風(bool UP) : Solver
648 {
649 Game g;
650 this(in Game g)
651 {
652 this.g = g.clone();
653 }
654
655 string plan;
656
657 char single_step()
658 {
659 auto dm = death_move(g);
660 if( plan.empty || dm[0].count(plan[0]) ) {
661 plan = think(g, dm[0]);
662 if( plan.empty )
663 plan = "W";
664 }
665
666 char c = plan[0];
667 plan = plan[1..$];
668
669 if(c == 'W') {
670 wait_counter++;
671 if(dm[0].count(c) || wait_counter>=3) {
672 c = 'A';
673 foreach(char cc; "DLRU")
674 if(dm[0].count(cc) == 0)
675 c = cc;
676 }
677 if(wait_counter > 20)
678 c = 'A';
679 } else {
680 wait_counter = 0;
681 }
682 if(c != 'A')
683 g.command(c);
684 return c;
685 }
686
687 void force(char c)
688 {
689 if(c != 'A')
690 g.command(c);
691 }
692
693 int wait_counter = 0;
694
695 string think(in Game g, string death)
696 {
697 auto Q = new Queue!(Tuple!(Pos,Pos));
698 Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0);
699 Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2);
700 while(!Q.empty) {
701 auto tup = Q.pop();
702 Pos p = tup[0][0];
703 Pos prev = tup[0][1];
704 int dist = tup[1];
705 if(V[p.y][p.x])
706 continue;
707 V[p.y][p.x] = prev;
708 if(g.map[p]=='\\' || g.map[p]=='O')
709 {
710 char[] trace;
711 for(;;) {
712 Pos q = V[p.y][p.x];
713 trace ~= (q.y==p.y ? (q.x<p.x ? 'R' : 'L') :
714 (q.y<p.y ? 'U' : 'D'));
715 if(q == g.map.robot) {
716 reverse(trace);
717 return trace.idup;
718 }
719 p=q;
720 }
721 }
722
723 int[4] dy=UP ? [+1,0,0,-1] : [-1,+1,0,0];
724 int[4] dx=UP ? [0,-1,+1,0] : [0,0,-1,+1];
725 char[] ds=UP ? ['U','L','R','D'] : ['D','U','L','R'];
726 for(int i=0; i<4; ++i) {
727 if(g.map.robot==p && death.count(ds[i]))
728 continue;
729 int y=p.y+dy[i], x=p.x+dx[i];
730 if((g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='O'||g.map[y,x]=='!')&&!V[y][x]) {
731 Q.push(tuple(new Pos(y,x),p), dist+1);
732 }
733 }
734 }
735
736 return "";
737 }
738 }
739
740 class Switcher
741 {
742 this(in Game g)
743 {
744 if(g.map.W*g.map.H <= 1600)
745 sub_solver = new 侵掠如火!(徐如林)(g);
746 else
747 sub_solver = new 侵掠如火!(疾如風!(true))(g);
748 }
749 char single_step() { return sub_solver.single_step(); }
750 void force(char c) { return sub_solver.force(c); }
751
752 private Solver sub_solver;
753 }
754
755 alias 侵掠如火!(疾如風!(false)) FastSolver;
756
757 alias Switcher MainSolver;
758 //alias 侵掠如火!(徐如林) MainSolver;