Index: src/game.d ================================================================== --- src/game.d +++ src/game.d @@ -147,11 +147,11 @@ if(y<0||H<=y||x<0||W<=x) return '#'; return data[H-1-y][x]; } - char opIndex(Pos p) + char opIndex(in Pos p) { return this[p.y, p.x]; } } @@ -162,11 +162,11 @@ if(y<0||H<=y||x<0||W<=x) return; data[H-1-y][x] = c; } - void opIndexAssign(char c, Pos p) + void opIndexAssign(char c, in Pos p) { this[p.y, p.x] = c; } Pos[] lambdas() const { Index: src/solver.d ================================================================== --- src/solver.d +++ src/solver.d @@ -49,25 +49,25 @@ { const Pos ro = g.map.robot; const Pos[] la = g.map.lambdas(); const Pos li = g.map.lift; + Tuple!(char,int)[] cand; char c = 'W'; if( la.empty ) { - auto r = search(g, ro, li, death); - c = r[0]; + cand = search(g, ro, li, death); } else { - Tuple!(char,int)[] cand; foreach(lam; la) cand ~= search(g, ro, lam, death); - sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ - if(c1[1] != c2[1]) - return c1[1] < c2[1]; - return c1[0] < c2[0]; - })(cand); - c = cand[0][0]; } + sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ + if(c1[1] != c2[1]) + return c1[1] < c2[1]; + return c1[0] < c2[0]; + })(cand); + c = cand[0][0]; + if(c=='W') { g_wc++; if(g_wc > 10) c = 'A'; } @@ -74,99 +74,118 @@ else g_wc = 0; return c; } - Tuple!(char,int) search(in Game g, in Pos s, in Pos o, string death) + Tuple!(char,int)[] search(in Game g, in Pos s, in Pos o, string death) { + bool danger(int y, int x) + { + if(g.map[y+1,x] == '*') + return true; + if(g.map[y+1,x-1]=='*' && (g.map[y,x-1]=='\\'||g.map[y,x-1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R')) + return true; + if(g.map[y+1,x+1]=='*' && (g.map[y,x+1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R')) + return true; + if(g.map[y,x-1]=='*' && (g.map[y-1,x-1]=='\\'||g.map[y-1,x-1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R')) + return true; + if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R')) + return true; + return false; + } + // avoid directly below '*' - const(Pos)[] q = [o]; - bool[][] v = new bool[][](g.map.H+2, g.map.W+2); - v[o.y][o.x]=true; - for(int step=1; q.length; ++step) { - Pos[] q2; - foreach(p; q) { - int[] dy=[-1,+1,0,0]; - int[] dx=[0,0,-1,+1]; - for(int i=0; i<4; ++i) { - int y = p.y+dy[i]; - int x = p.x+dx[i]; - if(v[y][x]) continue; - if(y==s.y && x==s.x) { - char c = "UDRL"[i]; - if( death.count(c) == 0 ) - return tuple(c,step); - } else if(g.map[y,x]==' '||g.map[y,x]=='\\') { - q2 ~= new Pos(y,x); - v[y][x]=true; - } else if(g.map[y,x]=='.' && g.map[y-1,x]!='*') { - q2 ~= new Pos(y,x); - v[y][x]=true; + Tuple!(char,int)[] tryA() { + const(Pos)[] q = [o]; + bool[][] v = new bool[][](g.map.H+2, g.map.W+2); + if( !danger(o.y,o.x) ) { + v[o.y][o.x]=true; + for(int step=1; q.length; ++step) { + Pos[] q2; + foreach(p; q) { + int[] dy=[-1,+1,0,0]; + int[] dx=[0,0,-1,+1]; + for(int i=0; i<4; ++i) { + int y = p.y+dy[i]; + int x = p.x+dx[i]; + if(v[y][x]) continue; + if(y==s.y && x==s.x) { + char c = "UDRL"[i]; + if( death.count(c) == 0 ) + return [tuple(c,step)]; + } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') { + if(danger(y,x)) + continue; + q2 ~= new Pos(y,x); + v[y][x]=true; + } + } } + q = q2; } } - q = q2; + return []; } // any empty space is my ground - q = [o]; - v = new bool[][](g.map.H+2, g.map.W+2); - v[o.y][o.x]=true; - for(int step=1000; q.length; ++step) { - Pos[] q2; - foreach(p; q) { - int[] dy=[-1,+1,0,0]; - int[] dx=[0,0,-1,+1]; - for(int i=0; i<4; ++i) { - int y = p.y+dy[i]; - int x = p.x+dx[i]; - if(v[y][x]) continue; - if(y==s.y && x==s.x) { - char c = "UDRL"[i]; - if( death.count(c) == 0 ) - return tuple(c,step); - } else if(g.map[y,x]==' '||g.map[y,x]=='\\') { - q2 ~= new Pos(y,x); - v[y][x]=true; - } else if(g.map[y,x]=='.'/* && g[y-1,x]!='*'*/) { - q2 ~= new Pos(y,x); - v[y][x]=true; + Tuple!(char,int)[] tryB() { + const(Pos)[] q = [o]; + bool[][] v = new bool[][](g.map.H+2, g.map.W+2); + v[o.y][o.x]=true; + for(int step=15; q.length; ++step) { + Pos[] q2; + foreach(p; q) { + int[] dy=[-1,+1,0,0]; + int[] dx=[0,0,-1,+1]; + for(int i=0; i<4; ++i) { + int y = p.y+dy[i]; + int x = p.x+dx[i]; + if(v[y][x]) continue; + if(y==s.y && x==s.x) { + char c = "UDRL"[i]; + if( death.count(c) == 0 ) + return [tuple(c,step)]; + } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') { + q2 ~= new Pos(y,x); + v[y][x]=true; + } } } + q = q2; } - q = q2; + return []; } // push rocks! - q = [o]; - v = new bool[][](g.map.H+2, g.map.W+2); - v[o.y][o.x]=true; - for(int step=2000; q.length; ++step) { - Pos[] q2; - foreach(p; q) { - int[] dy=[-1,+1,0,0]; - int[] dx=[0,0,-1,+1]; - for(int i=0; i<4; ++i) { - int y = p.y+dy[i]; - int x = p.x+dx[i]; - if(v[y][x]) continue; - if(y==s.y && x==s.x) { - char c = "UDRL"[i]; - if( death.count(c) == 0 ) - return tuple(c,step); - } else if(g.map[y,x]==' '||g.map[y,x]=='\\') { - q2 ~= new Pos(y,x); - v[y][x]=true; - } else if(g.map[y,x]=='.'/* && g[y-1,x]!='*'*/) { - q2 ~= new Pos(y,x); - v[y][x]=true; - } else if(dy[i]==0 && g.map[y,x]=='*' && (g.map[y+dy[i],x+dx[i]]==' '||g.map[y+dy[i],x+dx[i]]=='R')) { - q2 ~= new Pos(y,x); - v[y][x]=true; + Tuple!(char,int)[] tryC() { + const(Pos)[] q = [o]; + bool[][] v = new bool[][](g.map.H+2, g.map.W+2); + v[o.y][o.x]=true; + for(int step=30; q.length; ++step) { + Pos[] q2; + foreach(p; q) { + int[] dy=[-1,+1,0,0]; + int[] dx=[0,0,-1,+1]; + for(int i=0; i<4; ++i) { + int y = p.y+dy[i]; + int x = p.x+dx[i]; + if(v[y][x]) continue; + if(y==s.y && x==s.x) { + char c = "UDRL"[i]; + if( death.count(c) == 0 ) + return [tuple(c,step)]; + } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') { + q2 ~= new Pos(y,x); + v[y][x]=true; + } else if(dy[i]==0 && g.map[p]==' ' && g.map[y,x]=='*' && (g.map[y+dy[i],x+dx[i]]==' '||g.map[y+dy[i],x+dx[i]]=='R')) { + q2 ~= new Pos(y,x); + v[y][x]=true; + } } } + q = q2; } - q = q2; + return []; } - return tuple('W', int.max); + return tryA() ~ tryB() ~ tryC() ~ tuple('W', int.max); } }