Artifact 0bb4050087a6fb3f53ef5a516cd7759f02325de4:
0000: 69 6d 70 6f 72 74 20 75 74 69 6c 3b 0a 69 6d 70 import util;.imp
0010: 6f 72 74 20 67 61 6d 65 3b 0a 69 6d 70 6f 72 74 ort game;.import
0020: 20 64 72 69 76 65 72 3b 0a 0a 2f 2a 0a 69 6e 74 driver;../*.int
0030: 65 72 66 61 63 65 20 53 6f 6c 76 65 72 0a 7b 0a erface Solver.{.
0040: 09 74 68 69 73 28 63 6f 6e 73 74 28 47 61 6d 65 .this(const(Game
0050: 29 20 67 29 3b 0a 09 63 68 61 72 20 73 69 6e 67 ) g);..char sing
0060: 6c 65 5f 73 74 65 70 28 29 3b 0a 7d 0a 2a 2f 0a le_step();.}.*/.
0070: 0a 63 6c 61 73 73 20 53 6f 6c 76 65 72 5f 30 0a .class Solver_0.
0080: 7b 0a 09 74 68 69 73 28 63 6f 6e 73 74 28 47 61 {..this(const(Ga
0090: 6d 65 29 20 67 29 20 7b 7d 0a 09 63 68 61 72 20 me) g) {}..char
00a0: 73 69 6e 67 6c 65 5f 73 74 65 70 28 29 20 7b 20 single_step() {
00b0: 72 65 74 75 72 6e 20 27 57 27 3b 20 7d 0a 7d 0a return 'W'; }.}.
00c0: 0a 63 6c 61 73 73 20 53 6f 6c 76 65 72 5f 31 0a .class Solver_1.
00d0: 7b 0a 09 69 6e 74 20 67 5f 77 63 20 3d 20 30 3b {..int g_wc = 0;
00e0: 0a 0a 09 47 61 6d 65 20 67 3b 0a 09 74 68 69 73 ...Game g;..this
00f0: 28 63 6f 6e 73 74 28 47 61 6d 65 29 20 67 29 0a (const(Game) g).
0100: 09 7b 0a 09 09 74 68 69 73 2e 67 20 3d 20 67 2e .{...this.g = g.
0110: 63 6c 6f 6e 65 28 29 3b 0a 09 7d 0a 0a 09 63 68 clone();..}...ch
0120: 61 72 20 73 69 6e 67 6c 65 5f 73 74 65 70 28 29 ar single_step()
0130: 0a 09 7b 0a 09 09 63 68 61 72 20 63 20 3d 20 61 ..{...char c = a
0140: 63 74 28 67 29 3b 0a 09 09 67 2e 63 6f 6d 6d 61 ct(g);...g.comma
0150: 6e 64 28 63 29 3b 0a 09 09 72 65 74 75 72 6e 20 nd(c);...return
0160: 63 3b 0a 09 7d 0a 0a 09 63 68 61 72 20 61 63 74 c;..}...char act
0170: 28 63 6f 6e 73 74 28 47 61 6d 65 29 20 67 29 0a (const(Game) g).
0180: 09 7b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 20 20 .{...const Pos
0190: 20 72 6f 20 3d 20 67 2e 6d 61 70 2e 72 6f 62 6f ro = g.map.robo
01a0: 74 3b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 5b 5d t;...const Pos[]
01b0: 20 6c 61 20 3d 20 67 2e 6d 61 70 2e 6c 61 6d 62 la = g.map.lamb
01c0: 64 61 73 28 29 3b 0a 09 09 63 6f 6e 73 74 20 50 das();...const P
01d0: 6f 73 20 20 20 6c 69 20 3d 20 67 2e 6d 61 70 2e os li = g.map.
01e0: 6c 69 66 74 3b 0a 0a 09 09 63 68 61 72 20 63 20 lift;....char c
01f0: 3d 20 27 57 27 3b 0a 09 09 69 66 28 20 6c 61 2e = 'W';...if( la.
0200: 65 6d 70 74 79 20 29 20 7b 0a 09 09 09 61 75 74 empty ) {....aut
0210: 6f 20 72 20 3d 20 73 65 61 72 63 68 28 67 2c 20 o r = search(g,
0220: 72 6f 2c 20 6c 69 29 3b 0a 09 09 09 63 20 3d 20 ro, li);....c =
0230: 72 5b 30 5d 3b 0a 09 09 7d 20 65 6c 73 65 20 7b r[0];...} else {
0240: 0a 09 09 09 54 75 70 6c 65 21 28 63 68 61 72 2c ....Tuple!(char,
0250: 69 6e 74 29 5b 5d 20 63 61 6e 64 3b 0a 09 09 09 int)[] cand;....
0260: 66 6f 72 65 61 63 68 28 6c 61 6d 3b 20 6c 61 29 foreach(lam; la)
0270: 0a 09 09 09 09 63 61 6e 64 20 7e 3d 20 73 65 61 .....cand ~= sea
0280: 72 63 68 28 67 2c 20 72 6f 2c 20 6c 61 6d 29 3b rch(g, ro, lam);
0290: 0a 09 09 09 73 6f 72 74 21 28 28 54 75 70 6c 65 ....sort!((Tuple
02a0: 21 28 63 68 61 72 2c 69 6e 74 29 20 63 31 2c 20 !(char,int) c1,
02b0: 54 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 Tuple!(char,int)
02c0: 20 63 32 29 7b 0a 09 09 09 09 69 66 28 63 31 5b c2){.....if(c1[
02d0: 31 5d 20 21 3d 20 63 32 5b 31 5d 29 0a 09 09 09 1] != c2[1])....
02e0: 09 09 72 65 74 75 72 6e 20 63 31 5b 31 5d 20 3c ..return c1[1] <
02f0: 20 63 32 5b 31 5d 3b 0a 09 09 09 09 72 65 74 75 c2[1];.....retu
0300: 72 6e 20 63 31 5b 30 5d 20 3c 20 63 32 5b 30 5d rn c1[0] < c2[0]
0310: 3b 0a 09 09 09 7d 29 28 63 61 6e 64 29 3b 0a 09 ;....})(cand);..
0320: 09 09 63 20 3d 20 63 61 6e 64 5b 30 5d 5b 30 5d ..c = cand[0][0]
0330: 3b 0a 09 09 7d 0a 09 09 69 66 28 63 3d 3d 27 57 ;...}...if(c=='W
0340: 27 29 20 7b 0a 09 09 09 67 5f 77 63 2b 2b 3b 0a ') {....g_wc++;.
0350: 09 09 09 69 66 28 67 5f 77 63 20 3e 20 31 30 29 ...if(g_wc > 10)
0360: 0a 09 09 09 09 63 20 3d 20 27 41 27 3b 0a 09 09 .....c = 'A';...
0370: 7d 0a 09 09 65 6c 73 65 0a 09 09 09 67 5f 77 63 }...else....g_wc
0380: 20 3d 20 30 3b 0a 09 09 72 65 74 75 72 6e 20 63 = 0;...return c
0390: 3b 0a 09 7d 0a 0a 09 54 75 70 6c 65 21 28 63 68 ;..}...Tuple!(ch
03a0: 61 72 2c 69 6e 74 29 20 73 65 61 72 63 68 28 69 ar,int) search(i
03b0: 6e 20 47 61 6d 65 20 67 2c 20 69 6e 20 50 6f 73 n Game g, in Pos
03c0: 20 73 2c 20 69 6e 20 50 6f 73 20 6f 29 0a 09 7b s, in Pos o)..{
03d0: 0a 09 09 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 ...const(Pos)[]
03e0: 71 20 3d 20 5b 6f 5d 3b 0a 09 09 62 6f 6f 6c 5b q = [o];...bool[
03f0: 5d 5b 5d 20 76 20 3d 20 6e 65 77 20 62 6f 6f 6c ][] v = new bool
0400: 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 [][](g.map.H+2,
0410: 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 66 6f g.map.W+2);...fo
0420: 72 28 69 6e 74 20 73 74 65 70 3d 31 3b 20 71 2e r(int step=1; q.
0430: 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 29 20 length; ++step)
0440: 7b 0a 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a 09 {....Pos[] q2;..
0450: 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 ..foreach(p; q)
0460: 7b 0a 09 09 09 09 69 6e 74 5b 5d 20 64 79 3d 5b {.....int[] dy=[
0470: 2d 31 2c 2b 31 2c 30 2c 30 5d 3b 0a 09 09 09 09 -1,+1,0,0];.....
0480: 69 6e 74 5b 5d 20 64 78 3d 5b 30 2c 30 2c 2d 31 int[] dx=[0,0,-1
0490: 2c 2b 31 5d 3b 0a 09 09 09 09 66 6f 72 28 69 6e ,+1];.....for(in
04a0: 74 20 69 3d 30 3b 20 69 3c 34 3b 20 2b 2b 69 29 t i=0; i<4; ++i)
04b0: 20 7b 0a 09 09 09 09 09 69 6e 74 20 79 20 3d 20 {......int y =
04c0: 70 2e 79 2b 64 79 5b 69 5d 3b 0a 09 09 09 09 09 p.y+dy[i];......
04d0: 69 6e 74 20 78 20 3d 20 70 2e 78 2b 64 78 5b 69 int x = p.x+dx[i
04e0: 5d 3b 0a 09 09 09 09 09 69 66 28 76 5b 79 5d 5b ];......if(v[y][
04f0: 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 x]) continue;...
0500: 09 09 09 69 66 28 79 3d 3d 73 2e 79 20 26 26 20 ...if(y==s.y &&
0510: 78 3d 3d 73 2e 78 29 20 7b 0a 09 09 09 09 09 09 x==s.x) {.......
0520: 69 66 28 69 3d 3d 30 29 20 72 65 74 75 72 6e 20 if(i==0) return
0530: 74 75 70 6c 65 28 27 55 27 2c 73 74 65 70 29 3b tuple('U',step);
0540: 0a 09 09 09 09 09 09 69 66 28 69 3d 3d 31 29 20 .......if(i==1)
0550: 72 65 74 75 72 6e 20 74 75 70 6c 65 28 27 44 27 return tuple('D'
0560: 2c 73 74 65 70 29 3b 0a 09 09 09 09 09 09 69 66 ,step);.......if
0570: 28 69 3d 3d 32 29 20 72 65 74 75 72 6e 20 74 75 (i==2) return tu
0580: 70 6c 65 28 27 52 27 2c 73 74 65 70 29 3b 0a 09 ple('R',step);..
0590: 09 09 09 09 09 69 66 28 69 3d 3d 33 29 20 72 65 .....if(i==3) re
05a0: 74 75 72 6e 20 74 75 70 6c 65 28 27 4c 27 2c 73 turn tuple('L',s
05b0: 74 65 70 29 3b 0a 09 09 09 09 09 7d 20 65 6c 73 tep);......} els
05c0: 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d e if(g.map[y,x]=
05d0: 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d =' '||g.map[y,x]
05e0: 3d 3d 27 5c 5c 27 29 20 7b 0a 09 09 09 09 09 09 =='\\') {.......
05f0: 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c q2 ~= new Pos(y,
0600: 78 29 3b 0a 09 09 09 09 09 09 76 5b 79 5d 5b 78 x);.......v[y][x
0610: 5d 3d 74 72 75 65 3b 0a 09 09 09 09 09 7d 20 65 ]=true;......} e
0620: 6c 73 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78 lse if(g.map[y,x
0630: 5d 3d 3d 27 2e 27 20 26 26 20 67 2e 6d 61 70 5b ]=='.' && g.map[
0640: 79 2d 31 2c 78 5d 21 3d 27 2a 27 29 20 7b 0a 09 y-1,x]!='*') {..
0650: 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 50 .....q2 ~= new P
0660: 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 76 os(y,x);.......v
0670: 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09 [y][x]=true;....
0680: 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 7d 0a 09 ..}.....}....}..
0690: 09 09 71 20 3d 20 71 32 3b 0a 09 09 7d 0a 09 09 ..q = q2;...}...
06a0: 71 20 3d 20 5b 6f 5d 3b 0a 09 09 76 20 3d 20 6e q = [o];...v = n
06b0: 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 ew bool[][](g.ma
06c0: 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 p.H+2, g.map.W+2
06d0: 29 3b 0a 09 09 66 6f 72 28 69 6e 74 20 73 74 65 );...for(int ste
06e0: 70 3d 31 30 30 30 3b 20 71 2e 6c 65 6e 67 74 68 p=1000; q.length
06f0: 3b 20 2b 2b 73 74 65 70 29 20 7b 0a 09 09 09 50 ; ++step) {....P
0700: 6f 73 5b 5d 20 71 32 3b 0a 09 09 09 66 6f 72 65 os[] q2;....fore
0710: 61 63 68 28 70 3b 20 71 29 20 7b 0a 09 09 09 09 ach(p; q) {.....
0720: 69 6e 74 5b 5d 20 64 79 3d 5b 2d 31 2c 2b 31 2c int[] dy=[-1,+1,
0730: 30 2c 30 5d 3b 0a 09 09 09 09 69 6e 74 5b 5d 20 0,0];.....int[]
0740: 64 78 3d 5b 30 2c 30 2c 2d 31 2c 2b 31 5d 3b 0a dx=[0,0,-1,+1];.
0750: 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b ....for(int i=0;
0760: 20 69 3c 34 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 i<4; ++i) {....
0770: 09 09 69 6e 74 20 79 20 3d 20 70 2e 79 2b 64 79 ..int y = p.y+dy
0780: 5b 69 5d 3b 0a 09 09 09 09 09 69 6e 74 20 78 20 [i];......int x
0790: 3d 20 70 2e 78 2b 64 78 5b 69 5d 3b 0a 09 09 09 = p.x+dx[i];....
07a0: 09 09 69 66 28 76 5b 79 5d 5b 78 5d 29 20 63 6f ..if(v[y][x]) co
07b0: 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 69 66 28 ntinue;......if(
07c0: 79 3d 3d 73 2e 79 20 26 26 20 78 3d 3d 73 2e 78 y==s.y && x==s.x
07d0: 29 20 7b 0a 09 09 09 09 09 09 69 66 28 69 3d 3d ) {.......if(i==
07e0: 30 29 20 72 65 74 75 72 6e 20 74 75 70 6c 65 28 0) return tuple(
07f0: 27 55 27 2c 73 74 65 70 29 3b 0a 09 09 09 09 09 'U',step);......
0800: 09 69 66 28 69 3d 3d 31 29 20 72 65 74 75 72 6e .if(i==1) return
0810: 20 74 75 70 6c 65 28 27 44 27 2c 73 74 65 70 29 tuple('D',step)
0820: 3b 0a 09 09 09 09 09 09 69 66 28 69 3d 3d 32 29 ;.......if(i==2)
0830: 20 72 65 74 75 72 6e 20 74 75 70 6c 65 28 27 52 return tuple('R
0840: 27 2c 73 74 65 70 29 3b 0a 09 09 09 09 09 09 69 ',step);.......i
0850: 66 28 69 3d 3d 33 29 20 72 65 74 75 72 6e 20 74 f(i==3) return t
0860: 75 70 6c 65 28 27 4c 27 2c 73 74 65 70 29 3b 0a uple('L',step);.
0870: 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 67 .....} else if(g
0880: 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c 7c .map[y,x]==' '||
0890: 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c 27 g.map[y,x]=='\\'
08a0: 29 20 7b 0a 09 09 09 09 09 09 71 32 20 7e 3d 20 ) {.......q2 ~=
08b0: 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 new Pos(y,x);...
08c0: 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 ....v[y][x]=true
08d0: 3b 0a 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 ;......} else if
08e0: 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 (g.map[y,x]=='.'
08f0: 2f 2a 20 26 26 20 67 5b 79 2d 31 2c 78 5d 21 3d /* && g[y-1,x]!=
0900: 27 2a 27 2a 2f 29 20 7b 0a 09 09 09 09 09 09 71 '*'*/) {.......q
0910: 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c 78 2 ~= new Pos(y,x
0920: 29 3b 0a 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d );.......v[y][x]
0930: 3d 74 72 75 65 3b 0a 09 09 09 09 09 7d 0a 09 09 =true;......}...
0940: 09 09 7d 0a 09 09 09 7d 0a 09 09 09 71 20 3d 20 ..}....}....q =
0950: 71 32 3b 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e q2;...}...return
0960: 20 74 75 70 6c 65 28 27 57 27 2c 20 69 6e 74 2e tuple('W', int.
0970: 6d 61 78 29 3b 0a 09 7d 0a 7d 0a max);..}.}.