1 // 1 // 2 // http://en.wikipedia.org/wiki/F%C5%ABrinkazan 2 // http://en.wikipedia.org/wiki/F%C5%ABrinkazan 3 // 3 // 4 import util; 4 import util; 5 import game; 5 import game; > 6 > 7 > 8 interface Solver > 9 { > 10 // this(in Game g); > 11 char single_step(); > 12 void force(char c); > 13 } > 14 6 15 7 bool is_spacy(char c) 16 bool is_spacy(char c) 8 { 17 { 9 return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O'; 18 return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O'; 10 } 19 } 11 20 12 bool is_rocky(char c) 21 bool is_rocky(char c) ................................................................................................................................................................................ 95 death ~= ds[i]; 104 death ~= ds[i]; 96 } 105 } 97 } 106 } 98 107 99 return tuple(death, breath); 108 return tuple(death, breath); 100 } 109 } 101 110 102 interface Solver | 111 class Queue(T) 103 { 112 { 104 // this(in Game g); | 113 alias Tuple!(T,int) t; 105 char single_step(); < > 114 106 void force(char c); | 115 t[] cur, next; > 116 > 117 void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); } > 118 bool empty() { return cur.empty; } > 119 t pop() { > 120 t v = cur[0]; cur = cur[1..$]; > 121 if(cur.empty) { cur = next; next = null; } > 122 return v; > 123 } 107 } 124 } 108 125 109 /// 126 /// 110 /// Solver "Mountain": be immovable like a mountain. 127 /// Solver "Mountain": be immovable like a mountain. 111 /// 128 /// 112 class 不動如山 : Solver 129 class 不動如山 : Solver 113 { 130 { ................................................................................................................................................................................ 591 } 608 } 592 if(s.g.cleared) state = Fixed; 609 if(s.g.cleared) state = Fixed; 593 else if(s.g.dead) state = Tentative_Stuck; 610 else if(s.g.dead) state = Tentative_Stuck; 594 return tuple(s, log, state); 611 return tuple(s, log, state); 595 } 612 } 596 } 613 } 597 614 598 class Queue(T) < 599 { < 600 alias Tuple!(T,int) t; < 601 < 602 t[] cur, next; < 603 < 604 void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); } < 605 bool empty() { return cur.empty; } < 606 t pop() { < 607 t v = cur[0]; cur = cur[1..$]; < 608 if(cur.empty) { cur = next; next = null; } < 609 return v; < 610 } < 611 } < 612 < 613 /// 615 /// 614 /// Solver "Wind": let your rapidity be that of the wind. 616 /// Solver "Wind": let your rapidity be that of the wind. 615 /// 617 /// 616 class 疾如風 : Solver 618 class 疾如風 : Solver 617 { 619 { 618 Game g; 620 Game g; 619 this(in Game g) 621 this(in Game g) 620 { 622 { 621 this.g = g.clone(); 623 this.g = g.clone(); 622 } 624 } > 625 > 626 string plan; 623 627 624 char single_step() 628 char single_step() 625 { 629 { 626 auto dm = death_move(g); 630 auto dm = death_move(g); > 631 if( plan.empty || dm[0].count(plan[0]) ) { > 632 plan = think(g, dm[0]); > 633 if( plan.empty ) > 634 plan = "W"; > 635 } 627 636 628 char c = think(g, dm[0]); | 637 char c = plan[0]; > 638 plan = plan[1..$]; > 639 629 if(c == 'W') { 640 if(c == 'W') { 630 wait_counter++; 641 wait_counter++; 631 if(dm[0].count(c) || wait_counter>=3) { 642 if(dm[0].count(c) || wait_counter>=3) { 632 c = 'A'; 643 c = 'A'; 633 foreach(char cc; "DLRU") 644 foreach(char cc; "DLRU") 634 if(dm[0].count(cc) == 0) 645 if(dm[0].count(cc) == 0) 635 c = cc; 646 c = cc; ................................................................................................................................................................................ 648 { 659 { 649 if(c != 'A') 660 if(c != 'A') 650 g.command(c); 661 g.command(c); 651 } 662 } 652 663 653 int wait_counter = 0; 664 int wait_counter = 0; 654 665 655 char think(in Game g, string death) | 666 string think(in Game g, string death) 656 { 667 { 657 auto Q = new Queue!(Tuple!(Pos,Pos)); 668 auto Q = new Queue!(Tuple!(Pos,Pos)); 658 Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0); 669 Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0); 659 Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2); 670 Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2); 660 while(!Q.empty) { 671 while(!Q.empty) { 661 auto tup = Q.pop(); 672 auto tup = Q.pop(); 662 Pos p = tup[0][0]; 673 Pos p = tup[0][0]; ................................................................................................................................................................................ 663 Pos prev = tup[0][1]; 674 Pos prev = tup[0][1]; 664 int dist = tup[1]; 675 int dist = tup[1]; 665 if(V[p.y][p.x]) 676 if(V[p.y][p.x]) 666 continue; 677 continue; 667 V[p.y][p.x] = prev; 678 V[p.y][p.x] = prev; 668 if(g.map[p]=='\\' || g.map[p]=='O') 679 if(g.map[p]=='\\' || g.map[p]=='O') 669 { 680 { 670 Pos goback(Pos p) { | 681 char[] trace; 671 return V[p.y][p.x]; < 672 } < 673 for(;;) { 682 for(;;) { 674 Pos q = goback(p); | 683 Pos q = V[p.y][p.x]; > 684 trace ~= (q.y==p.y ? (q.x<p.x ? 'R' : 'L > 685 (q.y<p.y ? 'U' : 'D 675 if(q == g.map.robot) | 686 if(q == g.map.robot) { 676 if(q.y==p.y) < 677 return q.x<p.x ? 'R' : ' < 678 else | 687 reverse(trace); 679 return q.y<p.y ? 'U' : ' | 688 return trace.idup; > 689 } 680 p=q; 690 p=q; 681 } 691 } 682 } 692 } 683 693 684 int[4] dy=[-1,+1,0,0]; 694 int[4] dy=[-1,+1,0,0]; 685 int[4] dx=[0,0,-1,+1]; 695 int[4] dx=[0,0,-1,+1]; 686 char[] ds=['D','U','L','R']; 696 char[] ds=['D','U','L','R']; ................................................................................................................................................................................ 690 int y=p.y+dy[i], x=p.x+dx[i]; 700 int y=p.y+dy[i], x=p.x+dx[i]; 691 if((g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x 701 if((g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x 692 Q.push(tuple(new Pos(y,x),p), dist+1); 702 Q.push(tuple(new Pos(y,x),p), dist+1); 693 } 703 } 694 } 704 } 695 } 705 } 696 706 697 return 'W'; | 707 return ""; 698 } 708 } 699 } 709 } 700 710 701 //alias 侵掠如火!(疾如風) MainSolver; 711 //alias 侵掠如火!(疾如風) MainSolver; 702 //alias 侵掠如火!(徐如林) MainSolver; 712 //alias 侵掠如火!(徐如林) MainSolver; 703 alias 疾如風 MainSolver; 713 alias 疾如風 MainSolver; 704 //alias 徐如林 MainSolver; 714 //alias 徐如林 MainSolver; 705 //alias 不動如山 MainSolver; 715 //alias 不動如山 MainSolver;