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 foreach(char c; "UDLR")
170 if( death.count(c)==0 && is_one_way_load(g,c) )
171 return c;
172
173 const Pos ro = g.map.robot;
174 const Pos li = g.map.lift;
175 Pos[] la = g.map.lambdas();
176 sort!((Pos a,Pos b){
177 int ad=abs(a.y-li.y)+abs(a.x-li.x);
178 int bd=abs(b.y-li.y)+abs(b.x-li.x);
179 return ad>bd;;
180 })(la);
181 Pos[] ra = g.map.razors();
182 const(Pos)[] hi = g.map.objects('W');
183
184 Tuple!(char,int)[] cand;
185 char c = 'W';
186 if( g.map.collected_lambda == g.map.total_lambda ) {
187 cand = search(g, ro, [li], death);
188 } else if( !la.empty ){
189 cand ~= search(g, ro, la~ra, death);
190 }
191
192 // 'higesori' mode
193 if( !hi.empty && g.map.razor>0 ) {
194 int his = 0;
195 for(int dy=-1; dy<=+1; ++dy)
196 for(int dx=-1; dx<=+1; ++dx)
197 if(g.map[ro.y+dy,ro.x+dx] == 'W')
198 his++;
199
200 if(his>=2 || his==hi.length)
201 cand = [tuple('S',int.max)];
202 if(cand.empty) {
203 const(Pos)[] tgt;
204 for(int y=1; y<=g.map.H; ++y)
205 for(int x=1; x<=g.map.W; ++x)
206 if(g.map[y,x]=='.'||g.map[y,x]==' ') {
207 his = 0;
208 for(int dy=-1; dy<=+1; ++dy)
209 for(int dx=-1; dx<=+1; ++dx)
210 if(g.map[y+dy,x+dx] == 'W')
211 his++;
212 if(his>=2)
213 tgt ~= new Pos(y,x);
214 }
215 cand ~= search(g, ro, tgt, death, true);
216 }
217 }
218
219 // 'horo-push' mode
220 if(cand.empty) {
221 Pos[] horo = g.map.objects('@');
222 Pos[] tgt;
223 foreach(p; horo)
224 if((g.map[p.y,p.x-1]==' '||g.map[p.y,p.x-1]=='R')&&
225 (g.map[p.y,p.x+1]==' '||g.map[p.y,p.x+1]=='R')
226 ||(g.map[p.y-1,p.x]==' '||g.map[p.y-1,p.x]=='R'))
227 tgt ~= p;
228
229 for(int y=1; y<=g.map.H; ++y)
230 for(int x=1; x<=g.map.W; ++x)
231 if(g.map[y,x]=='.')
232 if(is_rocky(g.map[y+1,x])||is_rocky(g.map[y+1,x-1])||is_rocky(g.map[y+1,x+1])
233 ||is_rocky(g.map[y,x+1])||is_rocky(g.map[y,x-1]))
234 tgt ~= new Pos(y,x);
235
236 if(!tgt.empty)
237 cand ~= search(g, ro, tgt, death, true);
238 }
239
240 // 'dig' mode
241 if(cand.empty) {
242 Pos[] tgt;
243 for(int y=1; y<=g.map.H; ++y)
244 for(int x=1; x<=g.map.W; ++x)
245 if(g.map[y,x]=='.')
246 if(is_rocky(g.map[y+1,x])||is_rocky(g.map[y+1,x-1])||is_rocky(g.map[y+1,x+1])
247 ||is_rocky(g.map[y,x+1])||is_rocky(g.map[y,x-1]))
248 tgt ~= new Pos(y,x);
249 cand ~= search(g, ro, tgt, death, true);
250 }
251
252 if(cand.empty) {
253 choke_count++;
254 cand ~= tuple('W',int.max);
255 }
256 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
257 if(c1[1] != c2[1])
258 return c1[1] < c2[1];
259 return c1[0] < c2[0];
260 })(cand);
261 c = cand[0][0];
262
263 if(death.count(c) || wait_count>=2) {
264 foreach(char live; "UDLRW")
265 if(death.count(live)==0) {
266 c=live;
267 break;
268 }
269 }
270
271 if(c == 'W')
272 wait_count++;
273 else
274 wait_count = 0;
275 if(wait_count==2)
276 c = 'A';
277 if(choke_count >= g.map.H)
278 c = 'A';
279
280 bool[char] choice;
281 foreach(t; cand)
282 choice[t[0]] = true;
283 log ~= tuple(ro.clone(), cast(int)choice.length);
284 if(log.length > 5)
285 log = log[$-5..$];
286 int cnt = 0;
287 foreach(l; log)
288 if(l[0] == log[$-1][0])
289 ++cnt;
290 if( cnt >= 3 && breath==1 ) {
291 forbidden_cell[ro.y][ro.x] = true;
292 }
293
294 return c;
295 }
296
297 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death, bool danger_ok=false)
298 {
299 bool very_danger(int y, int x)
300 {
301 if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
302 return false;
303 if(is_rocky(g.map[y+1,x]))
304 return true;
305 return false;
306 }
307 bool danger(int y, int x)
308 {
309 if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
310 return false;
311 if(is_rocky(g.map[y+1,x]))
312 return true;
313 if(is_rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||is_rocky(g.map[y,x-1]))
314 && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
315 return true;
316 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'))
317 return true;
318 if(is_rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||is_rocky(g.map[y-1,x-1]))
319 && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
320 return true;
321 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'))
322 return true;
323 return false;
324 }
325
326 // avoid directly below '*'
327 Tuple!(char,int)[] tryA() {
328 const(Pos)[] q;
329 foreach(p; gs)
330 if(!very_danger(p.y,p.x))
331 q ~= p;
332 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
333 foreach(p; q) v[p.y][p.x]=true;
334 bool first_step = true;
335 for(int step=1; q.length; ++step) {
336 Pos[] q2;
337 foreach(p; q) {
338 int[] yyy=[p.y-1,p.y,p.y,p.y+1];
339 int[] xxx=[p.x,p.x-1,p.x+1,p.x];
340 string sss="URLD";
341 for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
342 int y = yyy[i];
343 int x = xxx[i];
344 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
345 foreach(ppp; g.tr.source_pos(g.map[y,x])) {
346 yyy ~= ppp.y;
347 xxx ~= ppp.x;
348 }
349 continue;
350 }
351 if(v[y][x]) continue;
352 if(y==s.y && x==s.x && i<4) {
353 char c = sss[i];
354 if( death.count(c) == 0 )
355 return [tuple(c,step)];
356 } else if(forbidden_cell[y][x]){
357 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
358 if(danger(y,x))
359 continue;
360 q2 ~= new Pos(y,x);
361 v[y][x]=true;
362 }
363 }
364 }
365 first_step = false;
366 q = q2;
367 }
368 return [];
369 }
370
371 // any empty space is my ground
372 Tuple!(char,int)[] tryB() {
373 const(Pos)[] q;
374 foreach(p; gs) q ~= p;
375 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
376 foreach(p; q) v[p.y][p.x]=true;
377 bool first_step = true;
378 for(int step=8; q.length; ++step) {
379 Pos[] q2;
380 foreach(p; q) {
381 int[] yyy=[p.y-1,p.y,p.y,p.y+1];
382 int[] xxx=[p.x,p.x-1,p.x+1,p.x];
383 string sss="URLD";
384 for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
385 int y = yyy[i];
386 int x = xxx[i];
387 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
388 foreach(ppp; g.tr.source_pos(g.map[y,x])) {
389 yyy ~= ppp.y;
390 xxx ~= ppp.x;
391 }
392 continue;
393 }
394 if(v[y][x]) continue;
395 if(y==s.y && x==s.x && i<4) {
396 char c = sss[i];
397 if( death.count(c) == 0 )
398 return [tuple(c,step)];
399 } else if(forbidden_cell[y][x]){
400 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
401 q2 ~= new Pos(y,x);
402 v[y][x]=true;
403 }
404 }
405 }
406 first_step = false;
407 q = q2;
408 }
409 return [];
410 }
411
412 // push rocks!
413 Tuple!(char,int)[] tryC() {
414 const(Pos)[] q;
415 foreach(p; gs) q ~= p;
416 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
417 foreach(p; q) v[p.y][p.x]=true;
418 bool first_step = true;
419 for(int step=20; q.length; ++step) {
420 Pos[] q2;
421 foreach(p; q) {
422 int[] yyy=[p.y-1,p.y,p.y,p.y+1];
423 int[] xxx=[p.x,p.x-1,p.x+1,p.x];
424 string sss="URLD";
425 for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
426 int y = yyy[i];
427 int x = xxx[i];
428 if(is_rocky(g.map[p])) {
429 if(i>=4)continue;
430 if(y!=p.y)continue;
431 if(g.map[y,p.x+(p.x-x)]!=' '&&g.map[y,p.x+(p.x-x)]!='R')continue;
432 }
433 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
434 foreach(ppp; g.tr.source_pos(g.map[y,x])) {
435 yyy ~= ppp.y;
436 xxx ~= ppp.x;
437 }
438 continue;
439 }
440 if(v[y][x]) continue;
441 if(y==s.y && x==s.x && i<4) {
442 char c = sss[i];
443 if( death.count(c) == 0 )
444 return [tuple(c,step)];
445 } else if(forbidden_cell[y][x]){
446 } 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) {
447 q2 ~= new Pos(y,x);
448 v[y][x]=true;
449 }
450 }
451 }
452 first_step = false;
453 q = q2;
454 }
455 return [];
456 }
457 return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
458 }
459
460 bool is_one_way_load(in Game g, char c)
461 {
462 Pos p = g.map.robot.clone();
463 Pos q;
464 if(c=='U') q=new Pos(p.y+1,p.x);
465 if(c=='D') q=new Pos(p.y-1,p.x);
466 if(c=='L') q=new Pos(p.y,p.x-1);
467 if(c=='R') q=new Pos(p.y,p.x+1);
468 char d = g.map[q];
469 if(!(d==' '||d=='.'||d=='!'))
470 return false;
471
472 bool found_lambda = false;
473 int[4] dy=[-1,+1,0,0];
474 int[4] dx=[0,0,+1,-1];
475 for(;;)
476 {
477 Pos r = null;
478 for(int i=0; i<4; ++i) {
479 int y=q.y+dy[i];
480 int x=q.x+dx[i];
481 if(x==p.x && y==p.y)
482 continue;
483 char e = g.map[y,x];
484 if(e=='#')
485 continue;
486 if(e==' '||e=='.'||e=='!'||e=='R'||e=='\\') {
487 if(r !is null)
488 return false;
489 r = new Pos(y,x);
490 if(e=='\\')
491 found_lambda = true;
492 continue;
493 }
494 return false;
495 }
496 if(r is null)
497 break;
498 p=q;
499 q=r;
500 }
501 return found_lambda;
502 }
503 }
504
505 ///
506 /// Solver "Fire": in raiding and plundering other solvers, be like fire.
507 ///
508 class 侵掠如火(SubSolver) : Solver
509 {
510 // Parameters.
511 int PredictFuture = 10;
512 const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL steps
513 const ReplanLength = 400; // O(PF*RCP*RL*SubSolver.single_step)
514
515 Game current_game;
516 SubSolver sub_solver;
517
518 enum {Tentative, Tentative_Stuck, Fixed};
519 string plan;
520 int plan_state;
521 int replan_limit;
522 bool lambda_getter;
523 int clear_improvement = 3;
524
525 this(in Game g)
526 {
527 current_game = g.clone();
528 plan = "";
529 plan_state = Tentative;
530 if(g.map.W*g.map.H <= 400) {
531 RandomChoicePattern = ["UU","UD","UL","UR",
532 "DU","DD","DL","DR",
533 "LU","LD","LL","LR",
534 "RU","RD","RL","RR","UUU","UUUU","UUUUU"];
535 PredictFuture = 20;
536 clear_improvement = 1;
537 }
538 else if(g.map.W*g.map.H <= 4096) {
539 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"];
540 PredictFuture = 10;
541 clear_improvement = 0;
542 }
543 else {
544 RandomChoicePattern = ["U","D","L","R"];
545 PredictFuture = 10;
546 clear_improvement = 0;
547 }
548
549 replan_limit = PredictFuture;
550 }
551
552 char single_step()
553 {
554 if(current_game.dead || current_game.cleared)
555 return 'A';
556
557 // Make enough prediction.
558 while( plan_state==Tentative && plan.length<replan_limit )
559 single_step_predict();
560
561 // If the future is bad, correct.
562 if( plan_state==Tentative_Stuck && plan.length<replan_limit && !lambda_getter )
563 replan();
564
565 // Follow the predicted plan.
566 if( plan.empty )
567 return 'A';
568 char c = plan[0];
569 plan = plan[1..$];
570 int b_lambda = current_game.map.collected_lambda;
571 current_game.command(c);
572 int a_lambda = current_game.map.collected_lambda;
573 if(b_lambda < a_lambda) lambda_getter = false;
574 return c;
575 }
576
577 void force(char c)
578 {
579 if(plan.length>0 && plan[0]==c)
580 {
581 // If matching the plan, just go forward.
582 plan = plan[1..$];
583 }
584 else
585 {
586 // Discard the plan, otherwise.
587 plan_state = Tentative;
588 plan = "";
589 sub_solver = null;
590 }
591 current_game.command(c);
592 }
593
594 void single_step_predict()
595 {
596 if(sub_solver is null) {
597 sub_solver = new SubSolver(current_game);
598 plan = "";
599 }
600
601 char c = sub_solver.single_step();
602 if(c == 'A')
603 plan_state = Tentative_Stuck;
604 else {
605 plan ~= c;
606 if(sub_solver.g.cleared) {
607 if(clear_improvement-->0) {
608 plan_state = Tentative_Stuck;
609 replan_limit = min(plan.length-plan.length/(clear_improvement+1), PredictFuture);
610 } else {
611 plan_state = Fixed;
612 }
613 } else {
614 plan_state = (sub_solver.g.dead ? Tentative_Stuck : Tentative);
615 }
616 }
617 }
618
619 void replan()
620 {
621 // Try to replace every step of the plan by another move.
622 Game g = current_game.clone();
623 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck);
624 int insertion_point = plan.length;
625 bool tiebreak_by_turn = false;
626 int consider_length = min(ReplanLength, g.map.W*g.map.H);
627 if(cand[0].g.cleared) consider_length = min(consider_length, cand[1].length);
628
629 for(int i=0; i<plan.length; ++i) {
630 foreach(string prefix; RandomChoicePattern)
631 if(prefix[0] != plan[i]) {
632 Tuple!(SubSolver, string, int) r = try_plan(g, prefix, consider_length-i-prefix.length);
633 r[1] = plan[0..i] ~ prefix ~ r[1];
634 bool better = false, tbt=false;
635 if(!cand[0].g.cleared && r[0].g.cleared)
636 better = true;
637 else if(cand[0].g.cleared && r[0].g.cleared) {
638 better = cand[0].g.score < r[0].g.score;
639 }
640 else if(!cand[0].g.cleared && !r[0].g.cleared) {
641 if(cand[0].g.map.collected_lambda < r[0].g.map.collected_lambda)
642 better = true;
643 else if(cand[0].g.map.collected_lambda == r[0].g.map.collected_lambda) {
644 if(cand[0].g.dead && !r[0].g.dead)
645 better = true;
646 else if(cand[0].g.dead == r[0].g.dead) {
647 better = (cand[1].length < r[1].length && r[2]!=Tentative_Stuck);
648 tbt = true;
649 }
650 }
651 }
652 if(better) {
653 cand = r;
654 tiebreak_by_turn = true;
655 insertion_point = i+prefix.length;
656 if(r[0].g.cleared) consider_length = min(consider_length, r[1].length);
657 }
658 }
659 g.command(plan[i]);
660 }
661
662 if(cand[2]==Fixed && insertion_point!=plan.length && clear_improvement-->0) {
663 sub_solver = cand[0];
664 plan = cand[1];
665 plan_state = Tentative_Stuck;
666 replan_limit = min(plan.length - insertion_point, PredictFuture);
667 lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
668 } else {
669 sub_solver = cand[0];
670 plan = cand[1];
671 plan_state = (plan.length < PredictFuture ? Fixed : cand[2]);
672 replan_limit = tiebreak_by_turn ? min(PredictFuture, (plan.length+1)/2) : PredictFuture;
673 lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
674 }
675 }
676
677 Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix, int consider_length)
678 {
679 if(consider_length<=0) consider_length = 2;
680
681 SubSolver s = new SubSolver(g);
682 foreach(char c; prefix)
683 s.force(c);
684 string log;
685 int state = Tentative;
686 while(!s.g.cleared && !s.g.dead && log.length<=consider_length) {
687 char c = s.single_step();
688 if( c == 'A' ) {
689 state = Tentative_Stuck;
690 break;
691 }
692 log ~= c;
693 }
694 if(s.g.cleared) state = Fixed;
695 else if(s.g.dead) state = Tentative_Stuck;
696 return tuple(s, log, state);
697 }
698 }
699
700 ///
701 /// Solver "Wind": let your rapidity be that of the wind.
702 ///
703 class 疾如風(bool UP) : Solver
704 {
705 Game g;
706 this(in Game g)
707 {
708 this.g = g.clone();
709 }
710
711 string plan;
712
713 char single_step()
714 {
715 auto dm = death_move(g);
716 if( plan.empty || dm[0].count(plan[0]) ) {
717 plan = think(g, dm[0]);
718 if( plan.empty )
719 plan = "W";
720 }
721
722 char c = plan[0];
723 plan = plan[1..$];
724
725 if(c == 'W') {
726 wait_counter++;
727 if(dm[0].count(c) || wait_counter>=3) {
728 c = 'A';
729 foreach(char cc; "DLRU")
730 if(dm[0].count(cc) == 0)
731 c = cc;
732 }
733 if(wait_counter > 20)
734 c = 'A';
735 } else {
736 wait_counter = 0;
737 }
738 if(c != 'A')
739 g.command(c);
740 return c;
741 }
742
743 void force(char c)
744 {
745 if(c != 'A')
746 g.command(c);
747 }
748
749 int wait_counter = 0;
750
751 string think(in Game g, string death)
752 {
753 auto Q = new Queue!(Tuple!(Pos,Pos));
754 Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0);
755 Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2);
756 while(!Q.empty) {
757 auto tup = Q.pop();
758 Pos p = tup[0][0];
759 Pos prev = tup[0][1];
760 int dist = tup[1];
761 if(V[p.y][p.x])
762 continue;
763 V[p.y][p.x] = prev;
764 if(g.map[p]=='\\' || g.map[p]=='O')
765 {
766 char[] trace;
767 for(;;) {
768 Pos q = V[p.y][p.x];
769 trace ~= (q.y==p.y ? (q.x<p.x ? 'R' : 'L') :
770 (q.y<p.y ? 'U' : 'D'));
771 if(q == g.map.robot) {
772 reverse(trace);
773 return trace.idup;
774 }
775 p=q;
776 }
777 }
778
779 int[4] dy=UP ? [+1,0,0,-1] : [-1,+1,0,0];
780 int[4] dx=UP ? [0,-1,+1,0] : [0,0,-1,+1];
781 char[] ds=UP ? ['U','L','R','D'] : ['D','U','L','R'];
782 for(int i=0; i<4; ++i) {
783 if(g.map.robot==p && death.count(ds[i]))
784 continue;
785 int y=p.y+dy[i], x=p.x+dx[i];
786 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]) {
787 Q.push(tuple(new Pos(y,x),p), dist+1);
788 }
789 }
790 }
791
792 return "";
793 }
794 }
795
796 class Switcher
797 {
798 this(in Game g)
799 {
800 if(g.map.W*g.map.H <= 1600)
801 sub_solver = new 侵掠如火!(徐如林)(g);
802 else
803 sub_solver = new 侵掠如火!(疾如風!(true))(g);
804 }
805 char single_step() { return sub_solver.single_step(); }
806 void force(char c) { return sub_solver.force(c); }
807
808 private Solver sub_solver;
809 }
810
811 alias 侵掠如火!(疾如風!(false)) FastSolver;
812
813 alias Switcher MainSolver;
814 //alias 徐如林 MainSolver;