Check-in [45f53ef26a]
Not logged in
Overview
SHA1 Hash:45f53ef26a810045b4bfef141eb436cce20259a3
Date: 2012-07-14 11:42:33
User: kinaba
Comment:Auto solver.
Timelines: family | ancestors | descendants | both | trunk
Diffs: redesign
Downloads: Tarball | ZIP archive
Other Links: files | file ages | manifest
Tags And Properties
Changes

Modified test.d from [2d52631f9ee4aac8] to [36818da9efe958b4].

195 case 'D': return command_D(); 195 case 'D': return command_D(); 196 case 'U': return command_U(); 196 case 'U': return command_U(); 197 case 'L': return command_L(); 197 case 'L': return command_L(); 198 case 'R': return command_R(); 198 case 'R': return command_R(); 199 case 'A': return abort(); 199 case 'A': return abort(); 200 default: return wait(); 200 default: return wait(); 201 } 201 } > 202 } else { > 203 Tuple!(char,int)[] cand; > 204 for(int i=0; i<ly.length; ++i) { > 205 auto r = search(sy,sx,ly[i],lx[i]); > 206 cand ~= r; > 207 } > 208 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ > 209 if(c1[1] != c2[1]) > 210 return c1[1] < c2[1]; > 211 return c1[0] < c2[0]; > 212 })(cand); > 213 switch(cand[0][0]) { > 214 case 'D': return command_D(); > 215 case 'U': return command_U(); > 216 case 'L': return command_L(); > 217 case 'R': return command_R(); > 218 case 'A': return abort(); > 219 default: return wait(); > 220 } 202 } 221 } 203 return wait(); 222 return wait(); 204 } 223 } 205 Tuple!(char,int) search(int sy, int sx, int oy, int ox) 224 Tuple!(char,int) search(int sy, int sx, int oy, int ox) 206 { 225 { 207 alias Tuple!(int,"y",int,"x") Pt; 226 alias Tuple!(int,"y",int,"x") Pt; 208 Pt[] q = [Pt(oy,ox)]; 227 Pt[] q = [Pt(oy,ox)]; > 228 bool[][] v = new bool[][](H,W); 209 for(int step=1; q.length; ++step) { 229 for(int step=1; q.length; ++step) { 210 Pt[] q2; 230 Pt[] q2; 211 foreach(p; q) { 231 foreach(p; q) { 212 < 213 int[] dy=[-1,+1,0,0]; 232 int[] dy=[-1,+1,0,0]; 214 int[] dx=[0,0,-1,+1]; 233 int[] dx=[0,0,-1,+1]; 215 for(int i=0; i<4; ++i) { 234 for(int i=0; i<4; ++i) { 216 int y = p.y+dy[i]; 235 int y = p.y+dy[i]; 217 int x = p.x+dx[i]; 236 int x = p.x+dx[i]; > 237 if(v[y][x]) continue; 218 if(y==sy && x==sx) { 238 if(y==sy && x==sx) { 219 if(i==0) return tuple('D',step); 239 if(i==0) return tuple('D',step); 220 if(i==1) return tuple('U',step); 240 if(i==1) return tuple('U',step); 221 if(i==2) return tuple('R',step); 241 if(i==2) return tuple('R',step); 222 if(i==3) return tuple('L',step); 242 if(i==3) return tuple('L',step); 223 } else if(data[y][x]==' '||data[y][x]==' 243 } else if(data[y][x]==' '||data[y][x]==' 224 q2 ~= Pt(y,x); 244 q2 ~= Pt(y,x); > 245 v[y][x]=true; 225 } else if(data[y][x]=='.' && data[y-1][x 246 } else if(data[y][x]=='.' && data[y-1][x 226 q2 ~= Pt(y,x); 247 q2 ~= Pt(y,x); > 248 v[y][x]=true; 227 } 249 } 228 } 250 } 229 } 251 } 230 q = q2; 252 q = q2; 231 } 253 } 232 q = [Pt(oy,ox)]; 254 q = [Pt(oy,ox)]; > 255 v = new bool[][](H,W); 233 for(int step=1<<10; q.length; ++step) { 256 for(int step=1<<10; q.length; ++step) { 234 Pt[] q2; 257 Pt[] q2; 235 foreach(p; q) { 258 foreach(p; q) { 236 259 237 int[] dy=[-1,+1,0,0]; 260 int[] dy=[-1,+1,0,0]; 238 int[] dx=[0,0,-1,+1]; 261 int[] dx=[0,0,-1,+1]; 239 for(int i=0; i<4; ++i) { 262 for(int i=0; i<4; ++i) { 240 int y = p.y+dy[i]; 263 int y = p.y+dy[i]; 241 int x = p.x+dx[i]; 264 int x = p.x+dx[i]; > 265 if(v[y][x]) continue; 242 if(y==sy && x==sx) { 266 if(y==sy && x==sx) { 243 if(i==0) return tuple('D',step); 267 if(i==0) return tuple('D',step); 244 if(i==1) return tuple('U',step); 268 if(i==1) return tuple('U',step); 245 if(i==2) return tuple('R',step); 269 if(i==2) return tuple('R',step); 246 if(i==3) return tuple('L',step); 270 if(i==3) return tuple('L',step); 247 } else if(data[y][x]==' '||data[y][x]==' 271 } else if(data[y][x]==' '||data[y][x]==' 248 q2 ~= Pt(y,x); 272 q2 ~= Pt(y,x); > 273 v[y][x]=true; 249 } else if(data[y][x]=='.'/* && data[y-1] 274 } else if(data[y][x]=='.'/* && data[y-1] 250 q2 ~= Pt(y,x); 275 q2 ~= Pt(y,x); > 276 v[y][x]=true; 251 } 277 } 252 } 278 } 253 } 279 } 254 q = q2; 280 q = q2; 255 } 281 } 256 return tuple('A',int.max); 282 return tuple('A',int.max); 257 } 283 }