1 import util; 1 import util; 2 import game; 2 import game; 3 import output; | 3 import driver; 4 4 5 int g_wc = 0; < 6 < 7 void act(Game g) < > 5 /* > 6 interface Solver 8 { 7 { 9 Pos ro = g.map.robot; | 8 this(const(Game) g); 10 Pos[] la = g.map.lambdas(); | 9 char single_step(); 11 Pos li = g.map.lift; < > 10 } > 11 */ 12 12 13 char c = 'W'; | 13 class Solver_0 14 if( la.empty ) { < > 14 { 15 auto r = search(g, ro, li); | 15 this(const(Game) g) {} 16 c = r[0]; | 16 char single_step() { return 'W'; } 17 } else { < 18 Tuple!(char,int)[] cand; < 19 foreach(lam; la) < 20 cand ~= search(g, ro, lam); < 21 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ < 22 if(c1[1] != c2[1]) < 23 return c1[1] < c2[1]; < 24 return c1[0] < c2[0]; < 25 })(cand); < 26 c = cand[0][0]; < 27 } < 28 if(c=='W') { < 29 g_wc++; < 30 if(g_wc > 10) < 31 c = 'A'; < 32 } < 33 else < 34 g_wc = 0; < 35 g.command(c); < 36 } 17 } 37 18 38 Tuple!(char,int) search(Game g, Pos s, Pos o) | 19 class Solver_1 39 { 20 { 40 Pos[] q = [o]; | 21 int g_wc = 0; 41 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); < > 22 42 for(int step=1; q.length; ++step) { | 23 Game g; 43 Pos[] q2; | 24 this(const(Game) g) 44 foreach(p; q) { < > 25 { 45 int[] dy=[-1,+1,0,0]; | 26 this.g = g.clone(); 46 int[] dx=[0,0,-1,+1]; < 47 for(int i=0; i<4; ++i) { < > 27 } > 28 48 int y = p.y+dy[i]; | 29 char single_step() 49 int x = p.x+dx[i]; < > 30 { 50 if(v[y][x]) continue; | 31 char c = act(g); 51 if(y==s.y && x==s.x) { | 32 g.command(c); 52 if(i==0) return tuple('U',step); | 33 return c; 53 if(i==1) return tuple('D',step); < 54 if(i==2) return tuple('R',step); < > 34 } > 35 55 if(i==3) return tuple('L',step); | 36 char act(const(Game) g) 56 } else if(g.map[y,x]==' '||g.map[y,x]=='\\') { < > 37 { 57 q2 ~= new Pos(y,x); | 38 const Pos ro = g.map.robot; 58 v[y][x]=true; | 39 const Pos[] la = g.map.lambdas(); 59 } else if(g.map[y,x]=='.' && g.map[y-1,x]!='*') | 40 const Pos li = g.map.lift; 60 q2 ~= new Pos(y,x); < 61 v[y][x]=true; < 62 } | 41 > 42 char c = 'W'; > 43 if( la.empty ) { > 44 auto r = search(g, ro, li); > 45 c = r[0]; > 46 } else { > 47 Tuple!(char,int)[] cand; > 48 foreach(lam; la) > 49 cand ~= search(g, ro, lam); > 50 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ > 51 if(c1[1] != c2[1]) > 52 return c1[1] < c2[1]; > 53 return c1[0] < c2[0]; > 54 })(cand); > 55 c = cand[0][0]; 63 } | 56 } > 57 if(c=='W') { > 58 g_wc++; > 59 if(g_wc > 10) > 60 c = 'A'; 64 } 61 } > 62 else 65 q = q2; | 63 g_wc = 0; > 64 return c; 66 } 65 } > 66 > 67 Tuple!(char,int) search(in Game g, in Pos s, in Pos o) > 68 { > 69 const(Pos)[] q = [o]; > 70 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); > 71 for(int step=1; q.length; ++step) { > 72 Pos[] q2; > 73 foreach(p; q) { > 74 int[] dy=[-1,+1,0,0]; > 75 int[] dx=[0,0,-1,+1]; > 76 for(int i=0; i<4; ++i) { > 77 int y = p.y+dy[i]; > 78 int x = p.x+dx[i]; > 79 if(v[y][x]) continue; > 80 if(y==s.y && x==s.x) { > 81 if(i==0) return tuple('U',step); > 82 if(i==1) return tuple('D',step); > 83 if(i==2) return tuple('R',step); > 84 if(i==3) return tuple('L',step); > 85 } else if(g.map[y,x]==' '||g.map[y,x]==' > 86 q2 ~= new Pos(y,x); > 87 v[y][x]=true; > 88 } else if(g.map[y,x]=='.' && g.map[y-1,x > 89 q2 ~= new Pos(y,x); > 90 v[y][x]=true; > 91 } > 92 } > 93 } > 94 q = q2; > 95 } 67 q = [o]; | 96 q = [o]; 68 v = new bool[][](g.map.H+2, g.map.W+2); | 97 v = new bool[][](g.map.H+2, g.map.W+2); 69 for(int step=1000; q.length; ++step) { | 98 for(int step=1000; q.length; ++step) { 70 Pos[] q2; | 99 Pos[] q2; 71 foreach(p; q) { | 100 foreach(p; q) { 72 int[] dy=[-1,+1,0,0]; | 101 int[] dy=[-1,+1,0,0]; 73 int[] dx=[0,0,-1,+1]; | 102 int[] dx=[0,0,-1,+1]; 74 for(int i=0; i<4; ++i) { | 103 for(int i=0; i<4; ++i) { 75 int y = p.y+dy[i]; | 104 int y = p.y+dy[i]; 76 int x = p.x+dx[i]; | 105 int x = p.x+dx[i]; 77 if(v[y][x]) continue; | 106 if(v[y][x]) continue; 78 if(y==s.y && x==s.x) { | 107 if(y==s.y && x==s.x) { 79 if(i==0) return tuple('U',step); | 108 if(i==0) return tuple('U',step); 80 if(i==1) return tuple('D',step); | 109 if(i==1) return tuple('D',step); 81 if(i==2) return tuple('R',step); | 110 if(i==2) return tuple('R',step); 82 if(i==3) return tuple('L',step); | 111 if(i==3) return tuple('L',step); 83 } else if(g.map[y,x]==' '||g.map[y,x]=='\\') { | 112 } else if(g.map[y,x]==' '||g.map[y,x]==' 84 q2 ~= new Pos(y,x); | 113 q2 ~= new Pos(y,x); 85 v[y][x]=true; | 114 v[y][x]=true; 86 } else if(g.map[y,x]=='.'/* && g[y-1,x]!='*'*/) | 115 } else if(g.map[y,x]=='.'/* && g[y-1,x]! 87 q2 ~= new Pos(y,x); | 116 q2 ~= new Pos(y,x); 88 v[y][x]=true; | 117 v[y][x]=true; > 118 } 89 } 119 } 90 } 120 } > 121 q = q2; 91 } 122 } 92 q = q2; | 123 return tuple('W', int.max); 93 } 124 } 94 return tuple('W', int.max); < 95 } < 96 < 97 void main(string[] args) < 98 { < 99 auto g = Game.load(stdin); < 100 g.set_output(new GuardedOutput(g)); < 101 < 102 while(!g.dead && !g.cleared) < 103 act(g); < 104 } 125 }