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