Artifact e22cb888fb6353ea3b88a418a8cd465a58c187a6:
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 2c 20 64 65 61 74 68 5f 6d 6f 76 65 ct(g, death_move
0150: 28 67 29 29 3b 0a 09 09 67 2e 63 6f 6d 6d 61 6e (g));...g.comman
0160: 64 28 63 29 3b 0a 09 09 72 65 74 75 72 6e 20 63 d(c);...return c
0170: 3b 0a 09 7d 0a 0a 09 73 74 72 69 6e 67 20 64 65 ;..}...string de
0180: 61 74 68 5f 6d 6f 76 65 28 63 6f 6e 73 74 28 47 ath_move(const(G
0190: 61 6d 65 29 20 67 29 0a 09 7b 0a 09 09 73 74 72 ame) g)..{...str
01a0: 69 6e 67 20 64 65 61 74 68 3b 0a 09 09 66 6f 72 ing death;...for
01b0: 65 61 63 68 28 63 68 61 72 20 63 3b 20 22 55 44 each(char c; "UD
01c0: 4c 52 57 22 29 20 7b 0a 09 09 09 47 61 6d 65 20 LRW") {....Game
01d0: 67 67 20 3d 20 67 2e 63 6c 6f 6e 65 28 29 3b 0a gg = g.clone();.
01e0: 09 09 09 67 67 2e 63 6f 6d 6d 61 6e 64 28 63 29 ...gg.command(c)
01f0: 3b 0a 09 09 09 69 66 28 20 21 67 67 2e 63 6c 65 ;....if( !gg.cle
0200: 61 72 65 64 20 26 26 20 67 67 2e 64 65 61 64 20 ared && gg.dead
0210: 29 0a 09 09 09 09 64 65 61 74 68 20 7e 3d 20 63 ).....death ~= c
0220: 3b 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e 20 64 ;...}...return d
0230: 65 61 74 68 3b 0a 09 7d 0a 0a 09 63 68 61 72 20 eath;..}...char
0240: 61 63 74 28 63 6f 6e 73 74 28 47 61 6d 65 29 20 act(const(Game)
0250: 67 2c 20 73 74 72 69 6e 67 20 64 65 61 74 68 29 g, string death)
0260: 0a 09 7b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 20 ..{...const Pos
0270: 20 20 72 6f 20 3d 20 67 2e 6d 61 70 2e 72 6f 62 ro = g.map.rob
0280: 6f 74 3b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 5b ot;...const Pos[
0290: 5d 20 6c 61 20 3d 20 67 2e 6d 61 70 2e 6c 61 6d ] la = g.map.lam
02a0: 62 64 61 73 28 29 3b 0a 09 09 63 6f 6e 73 74 20 bdas();...const
02b0: 50 6f 73 20 20 20 6c 69 20 3d 20 67 2e 6d 61 70 Pos li = g.map
02c0: 2e 6c 69 66 74 3b 0a 0a 09 09 63 68 61 72 20 63 .lift;....char c
02d0: 20 3d 20 27 57 27 3b 0a 09 09 69 66 28 20 6c 61 = 'W';...if( la
02e0: 2e 65 6d 70 74 79 20 29 20 7b 0a 09 09 09 61 75 .empty ) {....au
02f0: 74 6f 20 72 20 3d 20 73 65 61 72 63 68 28 67 2c to r = search(g,
0300: 20 72 6f 2c 20 6c 69 2c 20 64 65 61 74 68 29 3b ro, li, death);
0310: 0a 09 09 09 63 20 3d 20 72 5b 30 5d 3b 0a 09 09 ....c = r[0];...
0320: 7d 20 65 6c 73 65 20 7b 0a 09 09 09 54 75 70 6c } else {....Tupl
0330: 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d 20 63 e!(char,int)[] c
0340: 61 6e 64 3b 0a 09 09 09 66 6f 72 65 61 63 68 28 and;....foreach(
0350: 6c 61 6d 3b 20 6c 61 29 0a 09 09 09 09 63 61 6e lam; la).....can
0360: 64 20 7e 3d 20 73 65 61 72 63 68 28 67 2c 20 72 d ~= search(g, r
0370: 6f 2c 20 6c 61 6d 2c 20 64 65 61 74 68 29 3b 0a o, lam, death);.
0380: 09 09 09 73 6f 72 74 21 28 28 54 75 70 6c 65 21 ...sort!((Tuple!
0390: 28 63 68 61 72 2c 69 6e 74 29 20 63 31 2c 20 54 (char,int) c1, T
03a0: 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 20 uple!(char,int)
03b0: 63 32 29 7b 0a 09 09 09 09 69 66 28 63 31 5b 31 c2){.....if(c1[1
03c0: 5d 20 21 3d 20 63 32 5b 31 5d 29 0a 09 09 09 09 ] != c2[1]).....
03d0: 09 72 65 74 75 72 6e 20 63 31 5b 31 5d 20 3c 20 .return c1[1] <
03e0: 63 32 5b 31 5d 3b 0a 09 09 09 09 72 65 74 75 72 c2[1];.....retur
03f0: 6e 20 63 31 5b 30 5d 20 3c 20 63 32 5b 30 5d 3b n c1[0] < c2[0];
0400: 0a 09 09 09 7d 29 28 63 61 6e 64 29 3b 0a 09 09 ....})(cand);...
0410: 09 63 20 3d 20 63 61 6e 64 5b 30 5d 5b 30 5d 3b .c = cand[0][0];
0420: 0a 09 09 7d 0a 09 09 69 66 28 63 3d 3d 27 57 27 ...}...if(c=='W'
0430: 29 20 7b 0a 09 09 09 67 5f 77 63 2b 2b 3b 0a 09 ) {....g_wc++;..
0440: 09 09 69 66 28 67 5f 77 63 20 3e 20 31 30 29 0a ..if(g_wc > 10).
0450: 09 09 09 09 63 20 3d 20 27 41 27 3b 0a 09 09 7d ....c = 'A';...}
0460: 0a 09 09 65 6c 73 65 0a 09 09 09 67 5f 77 63 20 ...else....g_wc
0470: 3d 20 30 3b 0a 09 09 72 65 74 75 72 6e 20 63 3b = 0;...return c;
0480: 0a 09 7d 0a 0a 09 54 75 70 6c 65 21 28 63 68 61 ..}...Tuple!(cha
0490: 72 2c 69 6e 74 29 20 73 65 61 72 63 68 28 69 6e r,int) search(in
04a0: 20 47 61 6d 65 20 67 2c 20 69 6e 20 50 6f 73 20 Game g, in Pos
04b0: 73 2c 20 69 6e 20 50 6f 73 20 6f 2c 20 73 74 72 s, in Pos o, str
04c0: 69 6e 67 20 64 65 61 74 68 29 0a 09 7b 0a 09 09 ing death)..{...
04d0: 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 71 20 3d const(Pos)[] q =
04e0: 20 5b 6f 5d 3b 0a 09 09 62 6f 6f 6c 5b 5d 5b 5d [o];...bool[][]
04f0: 20 76 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b v = new bool[][
0500: 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d ](g.map.H+2, g.m
0510: 61 70 2e 57 2b 32 29 3b 0a 09 09 66 6f 72 28 69 ap.W+2);...for(i
0520: 6e 74 20 73 74 65 70 3d 31 3b 20 71 2e 6c 65 6e nt step=1; q.len
0530: 67 74 68 3b 20 2b 2b 73 74 65 70 29 20 7b 0a 09 gth; ++step) {..
0540: 09 09 50 6f 73 5b 5d 20 71 32 3b 0a 09 09 09 66 ..Pos[] q2;....f
0550: 6f 72 65 61 63 68 28 70 3b 20 71 29 20 7b 0a 09 oreach(p; q) {..
0560: 09 09 09 69 6e 74 5b 5d 20 64 79 3d 5b 2d 31 2c ...int[] dy=[-1,
0570: 2b 31 2c 30 2c 30 5d 3b 0a 09 09 09 09 69 6e 74 +1,0,0];.....int
0580: 5b 5d 20 64 78 3d 5b 30 2c 30 2c 2d 31 2c 2b 31 [] dx=[0,0,-1,+1
0590: 5d 3b 0a 09 09 09 09 66 6f 72 28 69 6e 74 20 69 ];.....for(int i
05a0: 3d 30 3b 20 69 3c 34 3b 20 2b 2b 69 29 20 7b 0a =0; i<4; ++i) {.
05b0: 09 09 09 09 09 69 6e 74 20 79 20 3d 20 70 2e 79 .....int y = p.y
05c0: 2b 64 79 5b 69 5d 3b 0a 09 09 09 09 09 69 6e 74 +dy[i];......int
05d0: 20 78 20 3d 20 70 2e 78 2b 64 78 5b 69 5d 3b 0a x = p.x+dx[i];.
05e0: 09 09 09 09 09 69 66 28 76 5b 79 5d 5b 78 5d 29 .....if(v[y][x])
05f0: 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 continue;......
0600: 69 66 28 79 3d 3d 73 2e 79 20 26 26 20 78 3d 3d if(y==s.y && x==
0610: 73 2e 78 29 20 7b 0a 09 09 09 09 09 09 63 68 61 s.x) {.......cha
0620: 72 20 63 20 3d 20 22 55 44 52 4c 22 5b 69 5d 3b r c = "UDRL"[i];
0630: 0a 09 09 09 09 09 09 69 66 28 20 64 65 61 74 68 .......if( death
0640: 2e 63 6f 75 6e 74 28 63 29 20 3d 3d 20 30 20 29 .count(c) == 0 )
0650: 0a 09 09 09 09 09 09 09 72 65 74 75 72 6e 20 74 ........return t
0660: 75 70 6c 65 28 63 2c 73 74 65 70 29 3b 0a 09 09 uple(c,step);...
0670: 09 09 09 7d 20 65 6c 73 65 20 69 66 28 67 2e 6d ...} else if(g.m
0680: 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e ap[y,x]==' '||g.
0690: 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c 27 29 20 map[y,x]=='\\')
06a0: 7b 0a 09 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 {.......q2 ~= ne
06b0: 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 w Pos(y,x);.....
06c0: 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a ..v[y][x]=true;.
06d0: 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 67 .....} else if(g
06e0: 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 20 26 .map[y,x]=='.' &
06f0: 26 20 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 21 3d & g.map[y-1,x]!=
0700: 27 2a 27 29 20 7b 0a 09 09 09 09 09 09 71 32 20 '*') {.......q2
0710: 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b ~= new Pos(y,x);
0720: 0a 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 .......v[y][x]=t
0730: 72 75 65 3b 0a 09 09 09 09 09 7d 0a 09 09 09 09 rue;......}.....
0740: 7d 0a 09 09 09 7d 0a 09 09 09 71 20 3d 20 71 32 }....}....q = q2
0750: 3b 0a 09 09 7d 0a 09 09 71 20 3d 20 5b 6f 5d 3b ;...}...q = [o];
0760: 0a 09 09 76 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b ...v = new bool[
0770: 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 ][](g.map.H+2, g
0780: 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 66 6f 72 .map.W+2);...for
0790: 28 69 6e 74 20 73 74 65 70 3d 31 30 30 30 3b 20 (int step=1000;
07a0: 71 2e 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 q.length; ++step
07b0: 29 20 7b 0a 09 09 09 50 6f 73 5b 5d 20 71 32 3b ) {....Pos[] q2;
07c0: 0a 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 ....foreach(p; q
07d0: 29 20 7b 0a 09 09 09 09 69 6e 74 5b 5d 20 64 79 ) {.....int[] dy
07e0: 3d 5b 2d 31 2c 2b 31 2c 30 2c 30 5d 3b 0a 09 09 =[-1,+1,0,0];...
07f0: 09 09 69 6e 74 5b 5d 20 64 78 3d 5b 30 2c 30 2c ..int[] dx=[0,0,
0800: 2d 31 2c 2b 31 5d 3b 0a 09 09 09 09 66 6f 72 28 -1,+1];.....for(
0810: 69 6e 74 20 69 3d 30 3b 20 69 3c 34 3b 20 2b 2b int i=0; i<4; ++
0820: 69 29 20 7b 0a 09 09 09 09 09 69 6e 74 20 79 20 i) {......int y
0830: 3d 20 70 2e 79 2b 64 79 5b 69 5d 3b 0a 09 09 09 = p.y+dy[i];....
0840: 09 09 69 6e 74 20 78 20 3d 20 70 2e 78 2b 64 78 ..int x = p.x+dx
0850: 5b 69 5d 3b 0a 09 09 09 09 09 69 66 28 76 5b 79 [i];......if(v[y
0860: 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a ][x]) continue;.
0870: 09 09 09 09 09 69 66 28 79 3d 3d 73 2e 79 20 26 .....if(y==s.y &
0880: 26 20 78 3d 3d 73 2e 78 29 20 7b 0a 09 09 09 09 & x==s.x) {.....
0890: 09 09 63 68 61 72 20 63 20 3d 20 22 55 44 52 4c ..char c = "UDRL
08a0: 22 5b 69 5d 3b 0a 09 09 09 09 09 09 69 66 28 20 "[i];.......if(
08b0: 64 65 61 74 68 2e 63 6f 75 6e 74 28 63 29 20 3d death.count(c) =
08c0: 3d 20 30 20 29 0a 09 09 09 09 09 09 09 72 65 74 = 0 )........ret
08d0: 75 72 6e 20 74 75 70 6c 65 28 63 2c 73 74 65 70 urn tuple(c,step
08e0: 29 3b 0a 09 09 09 09 09 7d 20 65 6c 73 65 20 69 );......} else i
08f0: 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 f(g.map[y,x]=='
0900: 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 '||g.map[y,x]=='
0910: 5c 5c 27 29 20 7b 0a 09 09 09 09 09 09 71 32 20 \\') {.......q2
0920: 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b ~= new Pos(y,x);
0930: 0a 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 .......v[y][x]=t
0940: 72 75 65 3b 0a 09 09 09 09 09 7d 20 65 6c 73 65 rue;......} else
0950: 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d if(g.map[y,x]==
0960: 27 2e 27 2f 2a 20 26 26 20 67 5b 79 2d 31 2c 78 '.'/* && g[y-1,x
0970: 5d 21 3d 27 2a 27 2a 2f 29 20 7b 0a 09 09 09 09 ]!='*'*/) {.....
0980: 09 09 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 ..q2 ~= new Pos(
0990: 79 2c 78 29 3b 0a 09 09 09 09 09 09 76 5b 79 5d y,x);.......v[y]
09a0: 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09 09 09 7d [x]=true;......}
09b0: 0a 09 09 09 09 7d 0a 09 09 09 7d 0a 09 09 09 71 .....}....}....q
09c0: 20 3d 20 71 32 3b 0a 09 09 7d 0a 09 09 72 65 74 = q2;...}...ret
09d0: 75 72 6e 20 74 75 70 6c 65 28 27 57 27 2c 20 69 urn tuple('W', i
09e0: 6e 74 2e 6d 61 78 29 3b 0a 09 7d 0a 7d 0a nt.max);..}.}.