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 0a 63 6c 61 73 73 ort game;..class
0020: 20 53 6f 6c 76 65 72 5f 30 0a 7b 0a 09 74 68 69 Solver_0.{..thi
0030: 73 28 69 6e 20 47 61 6d 65 20 67 29 20 7b 7d 0a s(in Game g) {}.
0040: 09 63 68 61 72 20 73 69 6e 67 6c 65 5f 73 74 65 .char single_ste
0050: 70 28 29 20 7b 20 72 65 74 75 72 6e 20 27 57 27 p() { return 'W'
0060: 3b 20 7d 0a 09 76 6f 69 64 20 66 6f 72 63 65 28 ; }..void force(
0070: 63 68 61 72 20 63 29 20 7b 7d 0a 7d 0a 2f 2a 0a char c) {}.}./*.
0080: 63 6c 61 73 73 20 53 6f 6c 76 65 72 5f 31 0a 7b class Solver_1.{
0090: 0a 09 69 6e 74 20 77 61 69 74 5f 63 6f 75 6e 74 ..int wait_count
00a0: 20 3d 20 30 3b 0a 09 69 6e 74 20 63 68 6f 6b 65 = 0;..int choke
00b0: 5f 63 6f 75 6e 74 20 3d 20 30 3b 0a 0a 09 47 61 _count = 0;...Ga
00c0: 6d 65 20 67 3b 0a 09 74 68 69 73 28 69 6e 20 47 me g;..this(in G
00d0: 61 6d 65 20 67 29 0a 09 7b 0a 09 09 74 68 69 73 ame g)..{...this
00e0: 2e 67 20 3d 20 67 2e 63 6c 6f 6e 65 28 29 3b 0a .g = g.clone();.
00f0: 09 09 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c ..forbidden_cell
0100: 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 = new bool[][](
0110: 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 g.map.H+2, g.map
0120: 2e 57 2b 32 29 3b 0a 09 7d 0a 0a 09 63 68 61 72 .W+2);..}...char
0130: 20 73 69 6e 67 6c 65 5f 73 74 65 70 28 29 0a 09 single_step()..
0140: 7b 0a 09 09 54 75 70 6c 65 21 28 73 74 72 69 6e {...Tuple!(strin
0150: 67 2c 69 6e 74 29 20 64 65 20 3d 20 64 65 61 74 g,int) de = deat
0160: 68 5f 6d 6f 76 65 28 67 29 3b 0a 09 09 63 68 61 h_move(g);...cha
0170: 72 20 63 20 3d 20 61 63 74 28 67 2c 20 64 65 5b r c = act(g, de[
0180: 30 5d 2c 20 64 65 5b 31 5d 29 3b 0a 09 09 66 6f 0], de[1]);...fo
0190: 72 63 65 28 63 29 3b 0a 09 09 72 65 74 75 72 6e rce(c);...return
01a0: 20 63 3b 0a 09 7d 0a 0a 09 76 6f 69 64 20 66 6f c;..}...void fo
01b0: 72 63 65 28 63 68 61 72 20 63 29 0a 09 7b 0a 09 rce(char c)..{..
01c0: 09 69 66 28 63 20 21 3d 20 27 41 27 29 0a 09 09 .if(c != 'A')...
01d0: 09 67 2e 63 6f 6d 6d 61 6e 64 28 63 29 3b 0a 09 .g.command(c);..
01e0: 7d 0a 0a 09 54 75 70 6c 65 21 28 73 74 72 69 6e }...Tuple!(strin
01f0: 67 2c 69 6e 74 29 20 64 65 61 74 68 5f 6d 6f 76 g,int) death_mov
0200: 65 28 63 6f 6e 73 74 28 47 61 6d 65 29 20 67 29 e(const(Game) g)
0210: 0a 09 7b 0a 09 09 73 74 72 69 6e 67 20 64 65 61 ..{...string dea
0220: 74 68 3b 0a 09 09 69 6e 74 20 63 68 6f 69 63 65 th;...int choice
0230: 20 3d 20 30 3b 0a 09 09 66 6f 72 65 61 63 68 28 = 0;...foreach(
0240: 63 68 61 72 20 63 3b 20 22 55 44 4c 52 57 22 29 char c; "UDLRW")
0250: 20 7b 0a 09 09 09 47 61 6d 65 20 67 67 20 3d 20 {....Game gg =
0260: 67 2e 63 6c 6f 6e 65 28 29 3b 0a 09 09 09 67 67 g.clone();....gg
0270: 2e 63 6f 6d 6d 61 6e 64 28 63 29 3b 0a 09 09 09 .command(c);....
0280: 69 66 28 20 21 67 67 2e 63 6c 65 61 72 65 64 20 if( !gg.cleared
0290: 26 26 20 67 67 2e 64 65 61 64 20 29 0a 09 09 09 && gg.dead )....
02a0: 09 64 65 61 74 68 20 7e 3d 20 63 3b 0a 09 09 09 .death ~= c;....
02b0: 65 6c 73 65 20 69 66 28 20 67 67 2e 6d 61 70 2e else if( gg.map.
02c0: 72 6f 62 6f 74 20 21 3d 20 67 2e 6d 61 70 2e 72 robot != g.map.r
02d0: 6f 62 6f 74 20 29 0a 09 09 09 09 63 68 6f 69 63 obot ).....choic
02e0: 65 2b 2b 3b 0a 09 09 09 65 6c 73 65 20 69 66 28 e++;....else if(
02f0: 20 63 20 21 3d 20 27 57 27 20 29 20 2f 2f 20 6d c != 'W' ) // m
0300: 65 61 6e 69 6e 67 6c 65 73 73 20 6d 6f 76 65 0a eaningless move.
0310: 09 09 09 09 64 65 61 74 68 20 7e 3d 20 63 3b 0a ....death ~= c;.
0320: 09 09 7d 0a 09 09 72 65 74 75 72 6e 20 74 75 70 ..}...return tup
0330: 6c 65 28 64 65 61 74 68 2c 20 63 68 6f 69 63 65 le(death, choice
0340: 29 3b 0a 09 7d 0a 0a 09 54 75 70 6c 65 21 28 50 );..}...Tuple!(P
0350: 6f 73 2c 20 69 6e 74 29 5b 5d 20 6c 6f 67 3b 0a os, int)[] log;.
0360: 09 62 6f 6f 6c 5b 5d 5b 5d 20 66 6f 72 62 69 64 .bool[][] forbid
0370: 64 65 6e 5f 63 65 6c 6c 3b 0a 0a 09 63 68 61 72 den_cell;...char
0380: 20 61 63 74 28 63 6f 6e 73 74 28 47 61 6d 65 29 act(const(Game)
0390: 20 67 2c 20 73 74 72 69 6e 67 20 64 65 61 74 68 g, string death
03a0: 2c 20 69 6e 74 20 62 72 65 61 74 68 29 0a 09 7b , int breath)..{
03b0: 0a 09 09 63 6f 6e 73 74 20 50 6f 73 20 20 20 20 ...const Pos
03c0: 72 6f 20 3d 20 67 2e 6d 61 70 2e 72 6f 62 6f 74 ro = g.map.robot
03d0: 3b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 20 20 20 ;...const Pos
03e0: 20 6c 69 20 3d 20 67 2e 6d 61 70 2e 6c 69 66 74 li = g.map.lift
03f0: 3b 0a 09 09 50 6f 73 5b 5d 20 6c 61 20 3d 20 67 ;...Pos[] la = g
0400: 2e 6d 61 70 2e 6c 61 6d 62 64 61 73 28 29 3b 0a .map.lambdas();.
0410: 09 09 73 6f 72 74 21 28 28 50 6f 73 20 61 2c 50 ..sort!((Pos a,P
0420: 6f 73 20 62 29 7b 0a 09 09 09 69 6e 74 20 61 64 os b){....int ad
0430: 3d 61 62 73 28 61 2e 79 2d 6c 69 2e 79 29 2b 61 =abs(a.y-li.y)+a
0440: 62 73 28 61 2e 78 2d 6c 69 2e 78 29 3b 0a 09 09 bs(a.x-li.x);...
0450: 09 69 6e 74 20 62 64 3d 61 62 73 28 62 2e 79 2d .int bd=abs(b.y-
0460: 6c 69 2e 79 29 2b 61 62 73 28 62 2e 78 2d 6c 69 li.y)+abs(b.x-li
0470: 2e 78 29 3b 0a 09 09 09 72 65 74 75 72 6e 20 61 .x);....return a
0480: 64 3e 62 64 3b 3b 0a 09 09 7d 29 28 6c 61 29 3b d>bd;;...})(la);
0490: 0a 09 09 50 6f 73 5b 5d 20 72 61 20 3d 20 67 2e ...Pos[] ra = g.
04a0: 6d 61 70 2e 72 61 7a 6f 72 73 28 29 3b 0a 09 09 map.razors();...
04b0: 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 68 69 20 const(Pos)[] hi
04c0: 3d 20 67 2e 6d 61 70 2e 6f 62 6a 65 63 74 73 28 = g.map.objects(
04d0: 27 57 27 29 3b 0a 0a 09 09 54 75 70 6c 65 21 28 'W');....Tuple!(
04e0: 63 68 61 72 2c 69 6e 74 29 5b 5d 20 63 61 6e 64 char,int)[] cand
04f0: 3b 0a 09 09 63 68 61 72 20 63 20 3d 20 27 57 27 ;...char c = 'W'
0500: 3b 0a 09 09 69 66 28 20 6c 61 2e 65 6d 70 74 79 ;...if( la.empty
0510: 20 29 20 7b 0a 09 09 09 63 61 6e 64 20 3d 20 73 ) {....cand = s
0520: 65 61 72 63 68 28 67 2c 20 72 6f 2c 20 5b 6c 69 earch(g, ro, [li
0530: 5d 2c 20 64 65 61 74 68 29 3b 0a 09 09 7d 20 65 ], death);...} e
0540: 6c 73 65 20 7b 0a 09 09 09 63 61 6e 64 20 7e 3d lse {....cand ~=
0550: 20 73 65 61 72 63 68 28 67 2c 20 72 6f 2c 20 6c search(g, ro, l
0560: 61 7e 72 61 2c 20 64 65 61 74 68 29 3b 0a 09 09 a~ra, death);...
0570: 7d 0a 0a 09 09 2f 2f 20 27 68 69 67 65 73 6f 72 }....// 'higesor
0580: 69 27 20 6d 6f 64 65 0a 09 09 69 66 28 20 21 68 i' mode...if( !h
0590: 69 2e 65 6d 70 74 79 20 26 26 20 67 2e 6d 61 70 i.empty && g.map
05a0: 2e 72 61 7a 6f 72 3e 30 20 29 20 7b 0a 09 09 09 .razor>0 ) {....
05b0: 69 6e 74 20 68 69 73 20 3d 20 30 3b 0a 09 09 09 int his = 0;....
05c0: 66 6f 72 28 69 6e 74 20 64 79 3d 2d 31 3b 20 64 for(int dy=-1; d
05d0: 79 3c 3d 2b 31 3b 20 2b 2b 64 79 29 0a 09 09 09 y<=+1; ++dy)....
05e0: 66 6f 72 28 69 6e 74 20 64 78 3d 2d 31 3b 20 64 for(int dx=-1; d
05f0: 78 3c 3d 2b 31 3b 20 2b 2b 64 78 29 0a 09 09 09 x<=+1; ++dx)....
0600: 09 69 66 28 67 2e 6d 61 70 5b 72 6f 2e 79 2b 64 .if(g.map[ro.y+d
0610: 79 2c 72 6f 2e 78 2b 64 78 5d 20 3d 3d 20 27 57 y,ro.x+dx] == 'W
0620: 27 29 0a 09 09 09 09 09 68 69 73 2b 2b 3b 0a 0a ')......his++;..
0630: 09 09 09 69 66 28 68 69 73 3e 3d 32 20 7c 7c 20 ...if(his>=2 ||
0640: 68 69 73 3d 3d 68 69 2e 6c 65 6e 67 74 68 29 0a his==hi.length).
0650: 09 09 09 09 63 61 6e 64 20 3d 20 5b 74 75 70 6c ....cand = [tupl
0660: 65 28 27 53 27 2c 69 6e 74 2e 6d 61 78 29 5d 3b e('S',int.max)];
0670: 0a 09 09 09 69 66 28 63 61 6e 64 2e 65 6d 70 74 ....if(cand.empt
0680: 79 29 20 7b 0a 09 09 09 09 63 6f 6e 73 74 28 50 y) {.....const(P
0690: 6f 73 29 5b 5d 20 74 67 74 3b 0a 09 09 09 09 66 os)[] tgt;.....f
06a0: 6f 72 28 69 6e 74 20 79 3d 31 3b 20 79 3c 3d 67 or(int y=1; y<=g
06b0: 2e 6d 61 70 2e 48 3b 20 2b 2b 79 29 0a 09 09 09 .map.H; ++y)....
06c0: 09 66 6f 72 28 69 6e 74 20 78 3d 31 3b 20 78 3c .for(int x=1; x<
06d0: 3d 67 2e 6d 61 70 2e 57 3b 20 2b 2b 78 29 0a 09 =g.map.W; ++x)..
06e0: 09 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2c 78 ....if(g.map[y,x
06f0: 5d 3d 3d 27 2e 27 7c 7c 67 2e 6d 61 70 5b 79 2c ]=='.'||g.map[y,
0700: 78 5d 3d 3d 27 20 27 29 20 7b 0a 09 09 09 09 09 x]==' ') {......
0710: 09 68 69 73 20 3d 20 30 3b 0a 09 09 09 09 09 09 .his = 0;.......
0720: 66 6f 72 28 69 6e 74 20 64 79 3d 2d 31 3b 20 64 for(int dy=-1; d
0730: 79 3c 3d 2b 31 3b 20 2b 2b 64 79 29 0a 09 09 09 y<=+1; ++dy)....
0740: 09 09 09 66 6f 72 28 69 6e 74 20 64 78 3d 2d 31 ...for(int dx=-1
0750: 3b 20 64 78 3c 3d 2b 31 3b 20 2b 2b 64 78 29 0a ; dx<=+1; ++dx).
0760: 09 09 09 09 09 09 09 69 66 28 67 2e 6d 61 70 5b .......if(g.map[
0770: 79 2b 64 79 2c 78 2b 64 78 5d 20 3d 3d 20 27 57 y+dy,x+dx] == 'W
0780: 27 29 0a 09 09 09 09 09 09 09 09 68 69 73 2b 2b ').........his++
0790: 3b 0a 09 09 09 09 09 09 69 66 28 68 69 73 3e 3d ;.......if(his>=
07a0: 32 29 0a 09 09 09 09 09 09 09 74 67 74 20 7e 3d 2)........tgt ~=
07b0: 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 new Pos(y,x);..
07c0: 09 09 09 09 7d 0a 09 09 09 09 63 61 6e 64 20 7e ....}.....cand ~
07d0: 3d 20 73 65 61 72 63 68 28 67 2c 20 72 6f 2c 20 = search(g, ro,
07e0: 74 67 74 2c 20 64 65 61 74 68 2c 20 74 72 75 65 tgt, death, true
07f0: 29 3b 0a 09 09 09 7d 0a 09 09 7d 0a 0a 09 09 2f );....}...}..../
0800: 2f 20 27 64 69 67 27 20 6d 6f 64 65 0a 09 09 69 / 'dig' mode...i
0810: 66 28 63 61 6e 64 2e 65 6d 70 74 79 29 20 7b 0a f(cand.empty) {.
0820: 09 09 09 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 ...const(Pos)[]
0830: 74 67 74 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 tgt;....for(int
0840: 79 3d 31 3b 20 79 3c 3d 67 2e 6d 61 70 2e 48 3b y=1; y<=g.map.H;
0850: 20 2b 2b 79 29 0a 09 09 09 66 6f 72 28 69 6e 74 ++y)....for(int
0860: 20 78 3d 31 3b 20 78 3c 3d 67 2e 6d 61 70 2e 57 x=1; x<=g.map.W
0870: 3b 20 2b 2b 78 29 0a 09 09 09 09 69 66 28 67 2e ; ++x).....if(g.
0880: 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 29 0a 09 map[y,x]=='.')..
0890: 09 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2b 31 ....if(g.map[y+1
08a0: 2c 78 5d 3d 3d 27 2a 27 7c 7c 67 2e 6d 61 70 5b ,x]=='*'||g.map[
08b0: 79 2b 31 2c 78 2d 31 5d 3d 3d 27 2a 27 7c 7c 67 y+1,x-1]=='*'||g
08c0: 2e 6d 61 70 5b 79 2b 31 2c 78 2b 31 5d 3d 3d 27 .map[y+1,x+1]=='
08d0: 2a 27 0a 09 09 09 09 09 20 7c 7c 67 2e 6d 61 70 *'...... ||g.map
08e0: 5b 79 2c 78 2b 31 5d 3d 3d 27 2a 27 7c 7c 67 2e [y,x+1]=='*'||g.
08f0: 6d 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27 2a 27 29 map[y,x-1]=='*')
0900: 0a 09 09 09 09 09 09 74 67 74 20 7e 3d 20 6e 65 .......tgt ~= ne
0910: 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 63 w Pos(y,x);....c
0920: 61 6e 64 20 7e 3d 20 73 65 61 72 63 68 28 67 2c and ~= search(g,
0930: 20 72 6f 2c 20 74 67 74 2c 20 64 65 61 74 68 2c ro, tgt, death,
0940: 20 74 72 75 65 29 3b 0a 09 09 7d 0a 0a 09 09 69 true);...}....i
0950: 66 28 63 61 6e 64 2e 65 6d 70 74 79 29 20 7b 0a f(cand.empty) {.
0960: 09 09 09 63 68 6f 6b 65 5f 63 6f 75 6e 74 2b 2b ...choke_count++
0970: 3b 0a 09 09 09 63 61 6e 64 20 7e 3d 20 74 75 70 ;....cand ~= tup
0980: 6c 65 28 27 57 27 2c 69 6e 74 2e 6d 61 78 29 3b le('W',int.max);
0990: 0a 09 09 7d 0a 09 09 73 6f 72 74 21 28 28 54 75 ...}...sort!((Tu
09a0: 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 20 63 ple!(char,int) c
09b0: 31 2c 20 54 75 70 6c 65 21 28 63 68 61 72 2c 69 1, Tuple!(char,i
09c0: 6e 74 29 20 63 32 29 7b 0a 09 09 09 69 66 28 63 nt) c2){....if(c
09d0: 31 5b 31 5d 20 21 3d 20 63 32 5b 31 5d 29 0a 09 1[1] != c2[1])..
09e0: 09 09 09 72 65 74 75 72 6e 20 63 31 5b 31 5d 20 ...return c1[1]
09f0: 3c 20 63 32 5b 31 5d 3b 0a 09 09 09 72 65 74 75 < c2[1];....retu
0a00: 72 6e 20 63 31 5b 30 5d 20 3c 20 63 32 5b 30 5d rn c1[0] < c2[0]
0a10: 3b 0a 09 09 7d 29 28 63 61 6e 64 29 3b 0a 09 09 ;...})(cand);...
0a20: 63 20 3d 20 63 61 6e 64 5b 30 5d 5b 30 5d 3b 0a c = cand[0][0];.
0a30: 0a 09 09 69 66 28 64 65 61 74 68 2e 63 6f 75 6e ...if(death.coun
0a40: 74 28 63 29 20 7c 7c 20 77 61 69 74 5f 63 6f 75 t(c) || wait_cou
0a50: 6e 74 3e 3d 32 29 20 7b 0a 09 09 09 66 6f 72 65 nt>=2) {....fore
0a60: 61 63 68 28 63 68 61 72 20 6c 69 76 65 3b 20 22 ach(char live; "
0a70: 55 44 4c 52 57 22 29 0a 09 09 09 09 69 66 28 64 UDLRW").....if(d
0a80: 65 61 74 68 2e 63 6f 75 6e 74 28 6c 69 76 65 29 eath.count(live)
0a90: 3d 3d 30 29 20 7b 0a 09 09 09 09 09 63 3d 6c 69 ==0) {......c=li
0aa0: 76 65 3b 0a 09 09 09 09 09 62 72 65 61 6b 3b 0a ve;......break;.
0ab0: 09 09 09 09 7d 0a 09 09 7d 0a 0a 09 09 69 66 28 ....}...}....if(
0ac0: 63 20 3d 3d 20 27 57 27 29 0a 09 09 09 77 61 69 c == 'W')....wai
0ad0: 74 5f 63 6f 75 6e 74 2b 2b 3b 0a 09 09 65 6c 73 t_count++;...els
0ae0: 65 0a 09 09 09 77 61 69 74 5f 63 6f 75 6e 74 20 e....wait_count
0af0: 3d 20 30 3b 0a 09 09 69 66 28 63 68 6f 6b 65 5f = 0;...if(choke_
0b00: 63 6f 75 6e 74 20 3e 3d 20 67 2e 6d 61 70 2e 48 count >= g.map.H
0b10: 29 0a 09 09 09 63 20 3d 20 27 41 27 3b 0a 0a 09 )....c = 'A';...
0b20: 09 62 6f 6f 6c 5b 63 68 61 72 5d 20 63 68 6f 69 .bool[char] choi
0b30: 63 65 3b 0a 09 09 66 6f 72 65 61 63 68 28 74 3b ce;...foreach(t;
0b40: 20 63 61 6e 64 29 0a 09 09 09 63 68 6f 69 63 65 cand)....choice
0b50: 5b 74 5b 30 5d 5d 20 3d 20 74 72 75 65 3b 0a 09 [t[0]] = true;..
0b60: 09 6c 6f 67 20 7e 3d 20 74 75 70 6c 65 28 72 6f .log ~= tuple(ro
0b70: 2e 63 6c 6f 6e 65 28 29 2c 20 63 61 73 74 28 69 .clone(), cast(i
0b80: 6e 74 29 63 68 6f 69 63 65 2e 6c 65 6e 67 74 68 nt)choice.length
0b90: 29 3b 0a 09 09 69 66 28 6c 6f 67 2e 6c 65 6e 67 );...if(log.leng
0ba0: 74 68 20 3e 20 35 29 0a 09 09 09 6c 6f 67 20 3d th > 5)....log =
0bb0: 20 6c 6f 67 5b 24 2d 35 2e 2e 24 5d 3b 0a 09 09 log[$-5..$];...
0bc0: 69 6e 74 20 63 6e 74 20 3d 20 30 3b 0a 09 09 66 int cnt = 0;...f
0bd0: 6f 72 65 61 63 68 28 6c 3b 20 6c 6f 67 29 0a 09 oreach(l; log)..
0be0: 09 09 69 66 28 6c 5b 30 5d 20 3d 3d 20 6c 6f 67 ..if(l[0] == log
0bf0: 5b 24 2d 31 5d 5b 30 5d 29 0a 09 09 09 09 2b 2b [$-1][0]).....++
0c00: 63 6e 74 3b 0a 09 09 69 66 28 20 63 6e 74 20 3e cnt;...if( cnt >
0c10: 3d 20 33 20 26 26 20 62 72 65 61 74 68 3d 3d 31 = 3 && breath==1
0c20: 20 29 20 7b 0a 09 09 09 66 6f 72 62 69 64 64 65 ) {....forbidde
0c30: 6e 5f 63 65 6c 6c 5b 72 6f 2e 79 5d 5b 72 6f 2e n_cell[ro.y][ro.
0c40: 78 5d 20 3d 20 74 72 75 65 3b 0a 09 09 7d 0a 0a x] = true;...}..
0c50: 09 09 72 65 74 75 72 6e 20 63 3b 0a 09 7d 0a 0a ..return c;..}..
0c60: 09 54 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 .Tuple!(char,int
0c70: 29 5b 5d 20 73 65 61 72 63 68 28 69 6e 20 47 61 )[] search(in Ga
0c80: 6d 65 20 67 2c 20 69 6e 20 50 6f 73 20 73 2c 20 me g, in Pos s,
0c90: 69 6e 20 50 6f 73 5b 5d 20 67 73 2c 20 73 74 72 in Pos[] gs, str
0ca0: 69 6e 67 20 64 65 61 74 68 2c 20 62 6f 6f 6c 20 ing death, bool
0cb0: 64 61 6e 67 65 72 5f 6f 6b 3d 66 61 6c 73 65 29 danger_ok=false)
0cc0: 0a 09 7b 0a 09 09 62 6f 6f 6c 20 64 61 6e 67 65 ..{...bool dange
0cd0: 72 28 69 6e 74 20 79 2c 20 69 6e 74 20 78 29 0a r(int y, int x).
0ce0: 09 09 7b 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b ..{....if(g.map[
0cf0: 79 2c 78 5d 20 3d 3d 20 27 20 27 20 7c 7c 20 67 y,x] == ' ' || g
0d00: 2e 6d 61 70 5b 79 2c 78 5d 20 3d 3d 20 27 52 27 .map[y,x] == 'R'
0d10: 29 0a 09 09 09 09 72 65 74 75 72 6e 20 66 61 6c ).....return fal
0d20: 73 65 3b 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b se;....if(g.map[
0d30: 79 2b 31 2c 78 5d 20 3d 3d 20 27 2a 27 29 0a 09 y+1,x] == '*')..
0d40: 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b 0a ...return true;.
0d50: 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2b 31 2c ...if(g.map[y+1,
0d60: 78 2d 31 5d 3d 3d 27 2a 27 20 26 26 20 28 67 2e x-1]=='*' && (g.
0d70: 6d 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27 5c 5c 27 map[y,x-1]=='\\'
0d80: 7c 7c 67 2e 6d 61 70 5b 79 2c 78 2d 31 5d 3d 3d ||g.map[y,x-1]==
0d90: 27 2a 27 29 20 26 26 20 28 67 2e 6d 61 70 5b 79 '*') && (g.map[y
0da0: 2b 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 +1,x]==' '||g.ma
0db0: 70 5b 79 2b 31 2c 78 5d 3d 3d 27 52 27 29 29 0a p[y+1,x]=='R')).
0dc0: 09 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b ....return true;
0dd0: 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2b 31 ....if(g.map[y+1
0de0: 2c 78 2b 31 5d 3d 3d 27 2a 27 20 26 26 20 28 67 ,x+1]=='*' && (g
0df0: 2e 6d 61 70 5b 79 2c 78 2b 31 5d 3d 3d 27 2a 27 .map[y,x+1]=='*'
0e00: 29 20 26 26 20 28 67 2e 6d 61 70 5b 79 2b 31 2c ) && (g.map[y+1,
0e10: 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 x]==' '||g.map[y
0e20: 2b 31 2c 78 5d 3d 3d 27 52 27 29 29 0a 09 09 09 +1,x]=='R'))....
0e30: 09 72 65 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 .return true;...
0e40: 09 69 66 28 67 2e 6d 61 70 5b 79 2c 78 2d 31 5d .if(g.map[y,x-1]
0e50: 3d 3d 27 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b =='*' && (g.map[
0e60: 79 2d 31 2c 78 2d 31 5d 3d 3d 27 5c 5c 27 7c 7c y-1,x-1]=='\\'||
0e70: 67 2e 6d 61 70 5b 79 2d 31 2c 78 2d 31 5d 3d 3d g.map[y-1,x-1]==
0e80: 27 2a 27 29 20 26 26 20 28 67 2e 6d 61 70 5b 79 '*') && (g.map[y
0e90: 2d 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 -1,x]==' '||g.ma
0ea0: 70 5b 79 2d 31 2c 78 5d 3d 3d 27 52 27 29 29 0a p[y-1,x]=='R')).
0eb0: 09 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b ....return true;
0ec0: 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2c 78 ....if(g.map[y,x
0ed0: 2b 31 5d 3d 3d 27 2a 27 20 26 26 20 28 67 2e 6d +1]=='*' && (g.m
0ee0: 61 70 5b 79 2d 31 2c 78 2b 31 5d 3d 3d 27 2a 27 ap[y-1,x+1]=='*'
0ef0: 29 20 26 26 20 28 67 2e 6d 61 70 5b 79 2d 31 2c ) && (g.map[y-1,
0f00: 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 x]==' '||g.map[y
0f10: 2d 31 2c 78 5d 3d 3d 27 52 27 29 29 0a 09 09 09 -1,x]=='R'))....
0f20: 09 72 65 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 .return true;...
0f30: 09 72 65 74 75 72 6e 20 66 61 6c 73 65 3b 0a 09 .return false;..
0f40: 09 7d 0a 0a 09 09 2f 2f 20 61 76 6f 69 64 20 64 .}....// avoid d
0f50: 69 72 65 63 74 6c 79 20 62 65 6c 6f 77 20 27 2a irectly below '*
0f60: 27 0a 09 09 54 75 70 6c 65 21 28 63 68 61 72 2c '...Tuple!(char,
0f70: 69 6e 74 29 5b 5d 20 74 72 79 41 28 29 20 7b 0a int)[] tryA() {.
0f80: 09 09 09 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 ...const(Pos)[]
0f90: 71 3b 0a 09 09 09 66 6f 72 65 61 63 68 28 70 3b q;....foreach(p;
0fa0: 20 67 73 29 0a 09 09 09 09 69 66 28 21 64 61 6e gs).....if(!dan
0fb0: 67 65 72 28 70 2e 79 2c 70 2e 78 29 29 0a 09 09 ger(p.y,p.x))...
0fc0: 09 09 09 71 20 7e 3d 20 70 3b 0a 09 09 09 62 6f ...q ~= p;....bo
0fd0: 6f 6c 5b 5d 5b 5d 20 76 20 3d 20 6e 65 77 20 62 ol[][] v = new b
0fe0: 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b ool[][](g.map.H+
0ff0: 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 2, g.map.W+2);..
1000: 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 ..foreach(p; q)
1010: 76 5b 70 2e 79 5d 5b 70 2e 78 5d 3d 74 72 75 65 v[p.y][p.x]=true
1020: 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 73 74 65 ;....for(int ste
1030: 70 3d 31 3b 20 71 2e 6c 65 6e 67 74 68 3b 20 2b p=1; q.length; +
1040: 2b 73 74 65 70 29 20 7b 0a 09 09 09 09 50 6f 73 +step) {.....Pos
1050: 5b 5d 20 71 32 3b 0a 09 09 09 09 66 6f 72 65 61 [] q2;.....forea
1060: 63 68 28 70 3b 20 71 29 20 7b 0a 09 09 09 09 09 ch(p; q) {......
1070: 69 6e 74 5b 5d 20 79 79 79 3d 5b 70 2e 79 2d 31 int[] yyy=[p.y-1
1080: 2c 70 2e 79 2b 31 2c 70 2e 79 2c 70 2e 79 5d 3b ,p.y+1,p.y,p.y];
1090: 0a 09 09 09 09 09 69 6e 74 5b 5d 20 78 78 78 3d ......int[] xxx=
10a0: 5b 70 2e 78 2c 70 2e 78 2c 70 2e 78 2d 31 2c 70 [p.x,p.x,p.x-1,p
10b0: 2e 78 2b 31 5d 3b 0a 09 09 09 09 09 66 6f 72 28 .x+1];......for(
10c0: 69 6e 74 20 69 3d 30 3b 20 69 3c 79 79 79 2e 6c int i=0; i<yyy.l
10d0: 65 6e 67 74 68 3b 20 2b 2b 69 29 20 7b 0a 09 09 ength; ++i) {...
10e0: 09 09 09 09 69 6e 74 20 79 20 3d 20 79 79 79 5b ....int y = yyy[
10f0: 69 5d 3b 0a 09 09 09 09 09 09 69 6e 74 20 78 20 i];.......int x
1100: 3d 20 78 78 78 5b 69 5d 3b 0a 09 09 09 09 09 09 = xxx[i];.......
1110: 69 66 28 27 31 27 3c 3d 67 2e 6d 61 70 5b 79 2c if('1'<=g.map[y,
1120: 78 5d 26 26 67 2e 6d 61 70 5b 79 2c 78 5d 3c 3d x]&&g.map[y,x]<=
1130: 27 39 27 29 20 7b 0a 09 09 09 09 09 09 09 66 6f '9') {........fo
1140: 72 65 61 63 68 28 70 70 70 3b 20 67 2e 6d 61 70 reach(ppp; g.map
1150: 2e 74 72 5f 73 6f 75 72 63 65 5b 67 2e 6d 61 70 .tr_source[g.map
1160: 5b 79 2c 78 5d 5d 29 20 7b 0a 09 09 09 09 09 09 [y,x]]) {.......
1170: 09 09 79 79 79 20 7e 3d 20 70 70 70 2e 79 3b 0a ..yyy ~= ppp.y;.
1180: 09 09 09 09 09 09 09 09 78 78 78 20 7e 3d 20 70 ........xxx ~= p
1190: 70 70 2e 78 3b 0a 09 09 09 09 09 09 09 7d 0a 09 pp.x;........}..
11a0: 09 09 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0a ......continue;.
11b0: 09 09 09 09 09 09 7d 0a 09 09 09 09 09 09 69 66 ......}.......if
11c0: 28 76 5b 79 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e (v[y][x]) contin
11d0: 75 65 3b 0a 09 09 09 09 09 09 69 66 28 79 3d 3d ue;.......if(y==
11e0: 73 2e 79 20 26 26 20 78 3d 3d 73 2e 78 20 26 26 s.y && x==s.x &&
11f0: 20 69 3c 34 29 20 7b 0a 09 09 09 09 09 09 09 63 i<4) {........c
1200: 68 61 72 20 63 20 3d 20 22 55 44 52 4c 22 5b 69 har c = "UDRL"[i
1210: 5d 3b 0a 09 09 09 09 09 09 09 69 66 28 20 64 65 ];........if( de
1220: 61 74 68 2e 63 6f 75 6e 74 28 63 29 20 3d 3d 20 ath.count(c) ==
1230: 30 20 29 0a 09 09 09 09 09 09 09 09 72 65 74 75 0 ).........retu
1240: 72 6e 20 5b 74 75 70 6c 65 28 63 2c 73 74 65 70 rn [tuple(c,step
1250: 29 5d 3b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 )];.......} else
1260: 20 69 66 28 66 6f 72 62 69 64 64 65 6e 5f 63 65 if(forbidden_ce
1270: 6c 6c 5b 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 09 ll[y][x]){......
1280: 09 7d 20 65 6c 73 65 20 69 66 28 67 2e 6d 61 70 .} else if(g.map
1290: 5b 79 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 [y,x]==' '||g.ma
12a0: 70 5b 79 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e p[y,x]=='\\'||g.
12b0: 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 7c 7c 67 map[y,x]=='.'||g
12c0: 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 21 27 7c 7c .map[y,x]=='!'||
12d0: 69 3e 3d 34 29 20 7b 0a 09 09 09 09 09 09 09 69 i>=4) {........i
12e0: 66 28 64 61 6e 67 65 72 28 79 2c 78 29 29 0a 09 f(danger(y,x))..
12f0: 09 09 09 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b .......continue;
1300: 0a 09 09 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 ........q2 ~= ne
1310: 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 w Pos(y,x);.....
1320: 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b ...v[y][x]=true;
1330: 0a 09 09 09 09 09 09 7d 0a 09 09 09 09 09 7d 0a .......}......}.
1340: 09 09 09 09 7d 0a 09 09 09 09 71 20 3d 20 71 32 ....}.....q = q2
1350: 3b 0a 09 09 09 7d 0a 09 09 09 72 65 74 75 72 6e ;....}....return
1360: 20 5b 5d 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 61 [];...}....// a
1370: 6e 79 20 65 6d 70 74 79 20 73 70 61 63 65 20 69 ny empty space i
1380: 73 20 6d 79 20 67 72 6f 75 6e 64 0a 09 09 54 75 s my ground...Tu
1390: 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d ple!(char,int)[]
13a0: 20 74 72 79 42 28 29 20 7b 0a 09 09 09 63 6f 6e tryB() {....con
13b0: 73 74 28 50 6f 73 29 5b 5d 20 71 3b 0a 09 09 09 st(Pos)[] q;....
13c0: 66 6f 72 65 61 63 68 28 70 3b 20 67 73 29 20 71 foreach(p; gs) q
13d0: 20 7e 3d 20 70 3b 0a 09 09 09 62 6f 6f 6c 5b 5d ~= p;....bool[]
13e0: 5b 5d 20 76 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b [] v = new bool[
13f0: 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 ][](g.map.H+2, g
1400: 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 09 66 6f .map.W+2);....fo
1410: 72 65 61 63 68 28 70 3b 20 71 29 20 76 5b 70 2e reach(p; q) v[p.
1420: 79 5d 5b 70 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 y][p.x]=true;...
1430: 09 66 6f 72 28 69 6e 74 20 73 74 65 70 3d 31 30 .for(int step=10
1440: 3b 20 71 2e 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 ; q.length; ++st
1450: 65 70 29 20 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 ep) {.....Pos[]
1460: 71 32 3b 0a 09 09 09 09 66 6f 72 65 61 63 68 28 q2;.....foreach(
1470: 70 3b 20 71 29 20 7b 0a 09 09 09 09 09 69 6e 74 p; q) {......int
1480: 5b 5d 20 79 79 79 3d 5b 70 2e 79 2d 31 2c 70 2e [] yyy=[p.y-1,p.
1490: 79 2b 31 2c 70 2e 79 2c 70 2e 79 5d 3b 0a 09 09 y+1,p.y,p.y];...
14a0: 09 09 09 69 6e 74 5b 5d 20 78 78 78 3d 5b 70 2e ...int[] xxx=[p.
14b0: 78 2c 70 2e 78 2c 70 2e 78 2d 31 2c 70 2e 78 2b x,p.x,p.x-1,p.x+
14c0: 31 5d 3b 0a 09 09 09 09 09 66 6f 72 28 69 6e 74 1];......for(int
14d0: 20 69 3d 30 3b 20 69 3c 79 79 79 2e 6c 65 6e 67 i=0; i<yyy.leng
14e0: 74 68 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 th; ++i) {......
14f0: 09 69 6e 74 20 79 20 3d 20 79 79 79 5b 69 5d 3b .int y = yyy[i];
1500: 0a 09 09 09 09 09 09 69 6e 74 20 78 20 3d 20 78 .......int x = x
1510: 78 78 5b 69 5d 3b 0a 09 09 09 09 09 09 69 66 28 xx[i];.......if(
1520: 27 31 27 3c 3d 67 2e 6d 61 70 5b 79 2c 78 5d 26 '1'<=g.map[y,x]&
1530: 26 67 2e 6d 61 70 5b 79 2c 78 5d 3c 3d 27 39 27 &g.map[y,x]<='9'
1540: 29 20 7b 0a 09 09 09 09 09 09 09 66 6f 72 65 61 ) {........forea
1550: 63 68 28 70 70 70 3b 20 67 2e 6d 61 70 2e 74 72 ch(ppp; g.map.tr
1560: 5f 73 6f 75 72 63 65 5b 67 2e 6d 61 70 5b 79 2c _source[g.map[y,
1570: 78 5d 5d 29 20 7b 0a 09 09 09 09 09 09 09 09 79 x]]) {.........y
1580: 79 79 20 7e 3d 20 70 70 70 2e 79 3b 0a 09 09 09 yy ~= ppp.y;....
1590: 09 09 09 09 09 78 78 78 20 7e 3d 20 70 70 70 2e .....xxx ~= ppp.
15a0: 78 3b 0a 09 09 09 09 09 09 09 7d 0a 09 09 09 09 x;........}.....
15b0: 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 ...continue;....
15c0: 09 09 09 7d 0a 09 09 09 09 09 09 69 66 28 76 5b ...}.......if(v[
15d0: 79 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b y][x]) continue;
15e0: 0a 09 09 09 09 09 09 69 66 28 79 3d 3d 73 2e 79 .......if(y==s.y
15f0: 20 26 26 20 78 3d 3d 73 2e 78 20 26 26 20 69 3c && x==s.x && i<
1600: 34 29 20 7b 0a 09 09 09 09 09 09 09 63 68 61 72 4) {........char
1610: 20 63 20 3d 20 22 55 44 52 4c 22 5b 69 5d 3b 0a c = "UDRL"[i];.
1620: 09 09 09 09 09 09 09 69 66 28 20 64 65 61 74 68 .......if( death
1630: 2e 63 6f 75 6e 74 28 63 29 20 3d 3d 20 30 20 29 .count(c) == 0 )
1640: 0a 09 09 09 09 09 09 09 09 72 65 74 75 72 6e 20 .........return
1650: 5b 74 75 70 6c 65 28 63 2c 73 74 65 70 29 5d 3b [tuple(c,step)];
1660: 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 .......} else if
1670: 28 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 5b (forbidden_cell[
1680: 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 09 09 7d 20 y][x]){.......}
1690: 65 6c 73 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c else if(g.map[y,
16a0: 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 x]==' '||g.map[y
16b0: 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 ,x]=='\\'||g.map
16c0: 5b 79 2c 78 5d 3d 3d 27 2e 27 7c 7c 67 2e 6d 61 [y,x]=='.'||g.ma
16d0: 70 5b 79 2c 78 5d 3d 3d 27 21 27 7c 7c 69 3e 3d p[y,x]=='!'||i>=
16e0: 34 29 20 7b 0a 09 09 09 09 09 09 09 71 32 20 7e 4) {........q2 ~
16f0: 3d 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a = new Pos(y,x);.
1700: 09 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 .......v[y][x]=t
1710: 72 75 65 3b 0a 09 09 09 09 09 09 7d 0a 09 09 09 rue;.......}....
1720: 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 09 71 20 ..}.....}.....q
1730: 3d 20 71 32 3b 0a 09 09 09 7d 0a 09 09 09 72 65 = q2;....}....re
1740: 74 75 72 6e 20 5b 5d 3b 0a 09 09 7d 0a 0a 09 09 turn [];...}....
1750: 2f 2f 20 70 75 73 68 20 72 6f 63 6b 73 21 0a 09 // push rocks!..
1760: 09 54 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 .Tuple!(char,int
1770: 29 5b 5d 20 74 72 79 43 28 29 20 7b 0a 09 09 09 )[] tryC() {....
1780: 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 71 3b 0a const(Pos)[] q;.
1790: 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 67 73 ...foreach(p; gs
17a0: 29 20 71 20 7e 3d 20 70 3b 0a 09 09 09 62 6f 6f ) q ~= p;....boo
17b0: 6c 5b 5d 5b 5d 20 76 20 3d 20 6e 65 77 20 62 6f l[][] v = new bo
17c0: 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 ol[][](g.map.H+2
17d0: 2c 20 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 , g.map.W+2);...
17e0: 09 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 76 .foreach(p; q) v
17f0: 5b 70 2e 79 5d 5b 70 2e 78 5d 3d 74 72 75 65 3b [p.y][p.x]=true;
1800: 0a 09 09 09 66 6f 72 28 69 6e 74 20 73 74 65 70 ....for(int step
1810: 3d 32 30 3b 20 71 2e 6c 65 6e 67 74 68 3b 20 2b =20; q.length; +
1820: 2b 73 74 65 70 29 20 7b 0a 09 09 09 09 50 6f 73 +step) {.....Pos
1830: 5b 5d 20 71 32 3b 0a 09 09 09 09 66 6f 72 65 61 [] q2;.....forea
1840: 63 68 28 70 3b 20 71 29 20 7b 0a 09 09 09 09 09 ch(p; q) {......
1850: 69 6e 74 5b 5d 20 79 79 79 3d 5b 70 2e 79 2d 31 int[] yyy=[p.y-1
1860: 2c 70 2e 79 2b 31 2c 70 2e 79 2c 70 2e 79 5d 3b ,p.y+1,p.y,p.y];
1870: 0a 09 09 09 09 09 69 6e 74 5b 5d 20 78 78 78 3d ......int[] xxx=
1880: 5b 70 2e 78 2c 70 2e 78 2c 70 2e 78 2d 31 2c 70 [p.x,p.x,p.x-1,p
1890: 2e 78 2b 31 5d 3b 0a 09 09 09 09 09 66 6f 72 28 .x+1];......for(
18a0: 69 6e 74 20 69 3d 30 3b 20 69 3c 79 79 79 2e 6c int i=0; i<yyy.l
18b0: 65 6e 67 74 68 3b 20 2b 2b 69 29 20 7b 0a 09 09 ength; ++i) {...
18c0: 09 09 09 09 69 6e 74 20 79 20 3d 20 79 79 79 5b ....int y = yyy[
18d0: 69 5d 3b 0a 09 09 09 09 09 09 69 6e 74 20 78 20 i];.......int x
18e0: 3d 20 78 78 78 5b 69 5d 3b 0a 09 09 09 09 09 09 = xxx[i];.......
18f0: 69 66 28 67 2e 6d 61 70 5b 70 5d 20 3d 3d 20 27 if(g.map[p] == '
1900: 2a 27 29 20 7b 0a 09 09 09 09 09 09 09 69 66 28 *') {........if(
1910: 69 3e 3d 34 29 63 6f 6e 74 69 6e 75 65 3b 0a 09 i>=4)continue;..
1920: 09 09 09 09 09 09 69 66 28 79 21 3d 70 2e 79 29 ......if(y!=p.y)
1930: 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 continue;.......
1940: 09 69 66 28 67 2e 6d 61 70 5b 79 2c 70 2e 78 2b .if(g.map[y,p.x+
1950: 28 70 2e 78 2d 78 29 5d 21 3d 27 20 27 26 26 67 (p.x-x)]!=' '&&g
1960: 2e 6d 61 70 5b 79 2c 70 2e 78 2b 28 70 2e 78 2d .map[y,p.x+(p.x-
1970: 78 29 5d 21 3d 27 52 27 29 63 6f 6e 74 69 6e 75 x)]!='R')continu
1980: 65 3b 0a 09 09 09 09 09 09 7d 0a 09 09 09 09 09 e;.......}......
1990: 09 69 66 28 27 31 27 3c 3d 67 2e 6d 61 70 5b 79 .if('1'<=g.map[y
19a0: 2c 78 5d 26 26 67 2e 6d 61 70 5b 79 2c 78 5d 3c ,x]&&g.map[y,x]<
19b0: 3d 27 39 27 29 20 7b 0a 09 09 09 09 09 09 09 66 ='9') {........f
19c0: 6f 72 65 61 63 68 28 70 70 70 3b 20 67 2e 6d 61 oreach(ppp; g.ma
19d0: 70 2e 74 72 5f 73 6f 75 72 63 65 5b 67 2e 6d 61 p.tr_source[g.ma
19e0: 70 5b 79 2c 78 5d 5d 29 20 7b 0a 09 09 09 09 09 p[y,x]]) {......
19f0: 09 09 09 79 79 79 20 7e 3d 20 70 70 70 2e 79 3b ...yyy ~= ppp.y;
1a00: 0a 09 09 09 09 09 09 09 09 78 78 78 20 7e 3d 20 .........xxx ~=
1a10: 70 70 70 2e 78 3b 0a 09 09 09 09 09 09 09 7d 0a ppp.x;........}.
1a20: 09 09 09 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b .......continue;
1a30: 0a 09 09 09 09 09 09 7d 0a 09 09 09 09 09 09 69 .......}.......i
1a40: 66 28 76 5b 79 5d 5b 78 5d 29 20 63 6f 6e 74 69 f(v[y][x]) conti
1a50: 6e 75 65 3b 0a 09 09 09 09 09 09 69 66 28 79 3d nue;.......if(y=
1a60: 3d 73 2e 79 20 26 26 20 78 3d 3d 73 2e 78 20 26 =s.y && x==s.x &
1a70: 26 20 69 3c 34 29 20 7b 0a 09 09 09 09 09 09 09 & i<4) {........
1a80: 63 68 61 72 20 63 20 3d 20 22 55 44 52 4c 22 5b char c = "UDRL"[
1a90: 69 5d 3b 0a 09 09 09 09 09 09 09 69 66 28 20 64 i];........if( d
1aa0: 65 61 74 68 2e 63 6f 75 6e 74 28 63 29 20 3d 3d eath.count(c) ==
1ab0: 20 30 20 29 0a 09 09 09 09 09 09 09 09 72 65 74 0 ).........ret
1ac0: 75 72 6e 20 5b 74 75 70 6c 65 28 63 2c 73 74 65 urn [tuple(c,ste
1ad0: 70 29 5d 3b 0a 09 09 09 09 09 09 7d 20 65 6c 73 p)];.......} els
1ae0: 65 20 69 66 28 66 6f 72 62 69 64 64 65 6e 5f 63 e if(forbidden_c
1af0: 65 6c 6c 5b 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 ell[y][x]){.....
1b00: 09 09 7d 20 65 6c 73 65 20 69 66 28 67 2e 6d 61 ..} else if(g.ma
1b10: 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d p[y,x]==' '||g.m
1b20: 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 ap[y,x]=='\\'||g
1b30: 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 7c 7c .map[y,x]=='.'||
1b40: 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2a 27 7c g.map[y,x]=='*'|
1b50: 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 21 27 |g.map[y,x]=='!'
1b60: 7c 7c 69 3e 3d 34 29 20 7b 0a 09 09 09 09 09 09 ||i>=4) {.......
1b70: 09 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 .q2 ~= new Pos(y
1b80: 2c 78 29 3b 0a 09 09 09 09 09 09 09 76 5b 79 5d ,x);........v[y]
1b90: 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09 09 09 09 [x]=true;.......
1ba0: 7d 0a 09 09 09 09 09 7d 0a 09 09 09 09 7d 0a 09 }......}.....}..
1bb0: 09 09 09 71 20 3d 20 71 32 3b 0a 09 09 09 7d 0a ...q = q2;....}.
1bc0: 09 09 09 72 65 74 75 72 6e 20 5b 5d 3b 0a 09 09 ...return [];...
1bd0: 7d 0a 09 09 72 65 74 75 72 6e 20 28 64 61 6e 67 }...return (dang
1be0: 65 72 5f 6f 6b 20 3f 20 5b 5d 20 3a 20 74 72 79 er_ok ? [] : try
1bf0: 41 28 29 29 20 7e 20 74 72 79 42 28 29 20 7e 20 A()) ~ tryB() ~
1c00: 74 72 79 43 28 29 3b 0a 09 7d 0a 7d 0a 0a 63 6c tryC();..}.}..cl
1c10: 61 73 73 20 53 6f 6c 76 65 72 5f 32 28 53 6f 6c ass Solver_2(Sol
1c20: 76 65 72 29 0a 7b 0a 09 73 74 72 69 6e 67 20 70 ver).{..string p
1c30: 6c 61 6e 3b 0a 09 62 6f 6f 6c 20 70 6c 61 6e 5f lan;..bool plan_
1c40: 62 72 6f 6b 65 6e 20 3d 20 74 72 75 65 3b 0a 0a broken = true;..
1c50: 09 47 61 6d 65 20 67 3b 0a 09 74 68 69 73 28 69 .Game g;..this(i
1c60: 6e 20 47 61 6d 65 20 67 29 0a 09 7b 0a 09 09 74 n Game g)..{...t
1c70: 68 69 73 2e 67 20 3d 20 67 2e 63 6c 6f 6e 65 28 his.g = g.clone(
1c80: 29 3b 0a 09 09 6d 61 6b 65 5f 70 6c 61 6e 28 67 );...make_plan(g
1c90: 29 3b 0a 09 7d 0a 0a 09 54 75 70 6c 65 21 28 53 );..}...Tuple!(S
1ca0: 6f 6c 76 65 72 2c 73 74 72 69 6e 67 29 20 72 75 olver,string) ru
1cb0: 6e 5f 73 75 62 5f 73 6f 6c 76 65 72 28 69 6e 20 n_sub_solver(in
1cc0: 47 61 6d 65 20 67 29 0a 09 7b 0a 09 09 73 74 72 Game g)..{...str
1cd0: 69 6e 67 20 6c 6f 67 3b 0a 09 09 61 75 74 6f 20 ing log;...auto
1ce0: 73 20 3d 20 6e 65 77 20 53 6f 6c 76 65 72 28 67 s = new Solver(g
1cf0: 29 3b 0a 09 09 77 68 69 6c 65 28 21 67 2e 63 6c );...while(!g.cl
1d00: 65 61 72 65 64 20 26 26 20 21 67 2e 64 65 61 64 eared && !g.dead
1d10: 20 26 26 20 70 6c 61 6e 2e 6c 65 6e 67 74 68 3c && plan.length<
1d20: 3d 67 2e 6d 61 70 2e 48 2a 67 2e 6d 61 70 2e 57 =g.map.H*g.map.W
1d30: 29 20 7b 0a 09 09 09 63 68 61 72 20 63 20 3d 20 ) {....char c =
1d40: 73 2e 73 69 6e 67 6c 65 5f 73 74 65 70 28 29 3b s.single_step();
1d50: 0a 09 09 09 69 66 28 20 63 20 3d 3d 20 27 41 27 ....if( c == 'A'
1d60: 20 29 0a 09 09 09 09 62 72 65 61 6b 3b 0a 09 09 ).....break;...
1d70: 09 6c 6f 67 20 7e 3d 20 63 3b 0a 09 09 7d 0a 09 .log ~= c;...}..
1d80: 09 77 68 69 6c 65 28 6c 6f 67 2e 6c 65 6e 67 74 .while(log.lengt
1d90: 68 3e 30 20 26 26 20 6c 6f 67 5b 24 2d 31 5d 3d h>0 && log[$-1]=
1da0: 3d 27 57 27 29 0a 09 09 09 6c 6f 67 2e 6c 65 6e ='W')....log.len
1db0: 67 74 68 2d 2d 3b 0a 09 09 72 65 74 75 72 6e 20 gth--;...return
1dc0: 74 75 70 6c 65 28 73 2c 20 6c 6f 67 29 3b 0a 09 tuple(s, log);..
1dd0: 7d 0a 0a 09 76 6f 69 64 20 6d 61 6b 65 5f 70 6c }...void make_pl
1de0: 61 6e 28 69 6e 20 47 61 6d 65 20 67 29 20 7b 0a an(in Game g) {.
1df0: 09 09 70 6c 61 6e 5f 62 72 6f 6b 65 6e 20 3d 20 ..plan_broken =
1e00: 66 61 6c 73 65 3b 0a 09 09 54 75 70 6c 65 21 28 false;...Tuple!(
1e10: 53 6f 6c 76 65 72 2c 73 74 72 69 6e 67 29 20 78 Solver,string) x
1e20: 20 3d 20 72 75 6e 5f 73 75 62 5f 73 6f 6c 76 65 = run_sub_solve
1e30: 72 28 67 29 3b 0a 09 09 70 6c 61 6e 20 3d 20 78 r(g);...plan = x
1e40: 5b 31 5d 3b 0a 09 09 69 66 28 78 5b 30 5d 2e 67 [1];...if(x[0].g
1e50: 2e 63 6c 65 61 72 65 64 29 0a 09 09 09 72 65 74 .cleared)....ret
1e60: 75 72 6e 3b 0a 09 09 6d 6f 64 69 66 79 5f 70 6c urn;...modify_pl
1e70: 61 6e 28 67 2c 20 78 5b 30 5d 2e 67 2e 73 63 6f an(g, x[0].g.sco
1e80: 72 65 29 3b 0a 09 7d 0a 0a 09 76 6f 69 64 20 6d re);..}...void m
1e90: 6f 64 69 66 79 5f 70 6c 61 6e 28 69 6e 20 47 61 odify_plan(in Ga
1ea0: 6d 65 20 69 6e 69 2c 20 6c 6f 6e 67 20 75 6e 6d me ini, long unm
1eb0: 6f 64 29 0a 09 7b 0a 09 09 69 6e 74 20 62 70 20 od)..{...int bp
1ec0: 3d 20 6d 61 78 28 30 2c 20 28 63 61 73 74 28 69 = max(0, (cast(i
1ed0: 6e 74 29 70 6c 61 6e 2e 6c 65 6e 67 74 68 29 2d nt)plan.length)-
1ee0: 31 30 29 3b 0a 09 09 47 61 6d 65 20 67 20 3d 20 10);...Game g =
1ef0: 69 6e 69 2e 63 6c 6f 6e 65 28 29 3b 0a 09 09 66 ini.clone();...f
1f00: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 62 70 or(int i=0; i<bp
1f10: 3b 20 2b 2b 69 29 20 67 2e 63 6f 6d 6d 61 6e 64 ; ++i) g.command
1f20: 28 70 6c 61 6e 5b 69 5d 29 3b 0a 0a 09 09 54 75 (plan[i]);....Tu
1f30: 70 6c 65 21 28 73 74 72 69 6e 67 2c 6c 6f 6e 67 ple!(string,long
1f40: 29 20 63 61 6e 64 20 3d 20 74 75 70 6c 65 28 70 ) cand = tuple(p
1f50: 6c 61 6e 2c 20 75 6e 6d 6f 64 29 3b 0a 09 09 66 lan, unmod);...f
1f60: 6f 72 28 69 6e 74 20 69 3d 62 70 3b 20 69 3c 70 or(int i=bp; i<p
1f70: 6c 61 6e 2e 6c 65 6e 67 74 68 3b 20 2b 2b 69 29 lan.length; ++i)
1f80: 20 7b 0a 09 09 09 66 6f 72 65 61 63 68 28 73 74 {....foreach(st
1f90: 72 69 6e 67 20 63 3b 20 5b 22 55 22 2c 22 44 22 ring c; ["U","D"
1fa0: 2c 22 4c 22 2c 22 52 22 2c 22 55 44 22 2c 22 44 ,"L","R","UD","D
1fb0: 55 22 2c 22 4c 52 22 2c 22 52 4c 22 5d 29 0a 09 U","LR","RL"])..
1fc0: 09 09 09 69 66 28 63 5b 30 5d 20 21 3d 20 70 6c ...if(c[0] != pl
1fd0: 61 6e 5b 69 5d 29 20 7b 0a 09 09 09 09 09 54 75 an[i]) {......Tu
1fe0: 70 6c 65 21 28 73 74 72 69 6e 67 2c 6c 6f 6e 67 ple!(string,long
1ff0: 29 20 7a 7a 20 3d 20 74 72 79 5f 70 6c 61 6e 28 ) zz = try_plan(
2000: 63 2c 20 67 29 3b 0a 09 09 09 09 09 69 66 28 63 c, g);......if(c
2010: 61 6e 64 5b 31 5d 3c 7a 7a 5b 31 5d 29 0a 09 09 and[1]<zz[1])...
2020: 09 09 09 09 63 61 6e 64 20 3d 20 74 75 70 6c 65 ....cand = tuple
2030: 28 70 6c 61 6e 5b 30 2e 2e 69 5d 7e 63 7e 7a 7a (plan[0..i]~c~zz
2040: 5b 30 5d 2c 20 7a 7a 5b 31 5d 29 3b 0a 09 09 09 [0], zz[1]);....
2050: 09 7d 0a 09 09 09 67 2e 63 6f 6d 6d 61 6e 64 28 .}....g.command(
2060: 70 6c 61 6e 5b 69 5d 29 3b 0a 09 09 7d 0a 09 09 plan[i]);...}...
2070: 70 6c 61 6e 20 3d 20 63 61 6e 64 5b 30 5d 3b 0a plan = cand[0];.
2080: 09 7d 0a 0a 09 54 75 70 6c 65 21 28 73 74 72 69 .}...Tuple!(stri
2090: 6e 67 2c 6c 6f 6e 67 29 20 74 72 79 5f 70 6c 61 ng,long) try_pla
20a0: 6e 28 73 74 72 69 6e 67 20 63 2c 20 69 6e 20 47 n(string c, in G
20b0: 61 6d 65 20 67 29 0a 09 7b 0a 09 09 47 61 6d 65 ame g)..{...Game
20c0: 20 67 67 20 3d 20 67 2e 63 6c 6f 6e 65 28 29 3b gg = g.clone();
20d0: 0a 09 09 66 6f 72 65 61 63 68 28 63 63 3b 63 29 ...foreach(cc;c)
20e0: 67 67 2e 63 6f 6d 6d 61 6e 64 28 63 63 29 3b 0a gg.command(cc);.
20f0: 09 09 54 75 70 6c 65 21 28 53 6f 6c 76 65 72 2c ..Tuple!(Solver,
2100: 20 73 74 72 69 6e 67 29 20 78 20 3d 20 72 75 6e string) x = run
2110: 5f 73 75 62 5f 73 6f 6c 76 65 72 28 67 67 29 3b _sub_solver(gg);
2120: 0a 09 09 72 65 74 75 72 6e 20 74 75 70 6c 65 28 ...return tuple(
2130: 78 5b 31 5d 2c 20 78 5b 30 5d 2e 67 2e 73 63 6f x[1], x[0].g.sco
2140: 72 65 29 3b 0a 09 7d 0a 0a 09 63 68 61 72 20 73 re);..}...char s
2150: 69 6e 67 6c 65 5f 73 74 65 70 28 29 20 7b 0a 09 ingle_step() {..
2160: 09 69 66 28 70 6c 61 6e 5f 62 72 6f 6b 65 6e 29 .if(plan_broken)
2170: 0a 09 09 09 6d 61 6b 65 5f 70 6c 61 6e 28 67 29 ....make_plan(g)
2180: 3b 0a 09 09 69 66 28 70 6c 61 6e 2e 65 6d 70 74 ;...if(plan.empt
2190: 79 29 0a 09 09 09 72 65 74 75 72 6e 20 27 41 27 y)....return 'A'
21a0: 3b 0a 09 09 63 68 61 72 20 63 20 3d 20 70 6c 61 ;...char c = pla
21b0: 6e 5b 30 5d 3b 0a 09 09 70 6c 61 6e 20 3d 20 70 n[0];...plan = p
21c0: 6c 61 6e 5b 31 2e 2e 24 5d 3b 0a 09 09 67 2e 63 lan[1..$];...g.c
21d0: 6f 6d 6d 61 6e 64 28 63 29 3b 0a 09 09 72 65 74 ommand(c);...ret
21e0: 75 72 6e 20 63 3b 0a 09 7d 0a 0a 09 76 6f 69 64 urn c;..}...void
21f0: 20 66 6f 72 63 65 28 63 68 61 72 20 63 29 20 7b force(char c) {
2200: 0a 09 09 67 2e 63 6f 6d 6d 61 6e 64 28 63 29 3b ...g.command(c);
2210: 0a 09 09 69 66 28 70 6c 61 6e 2e 6c 65 6e 67 74 ...if(plan.lengt
2220: 68 3d 3d 30 20 7c 7c 20 70 6c 61 6e 5b 30 5d 21 h==0 || plan[0]!
2230: 3d 63 29 20 7b 0a 09 09 09 70 6c 61 6e 20 3d 20 =c) {....plan =
2240: 22 22 3b 0a 09 09 09 70 6c 61 6e 5f 62 72 6f 6b "";....plan_brok
2250: 65 6e 20 3d 20 74 72 75 65 3b 0a 09 09 7d 0a 09 en = true;...}..
2260: 09 65 6c 73 65 0a 09 09 09 70 6c 61 6e 20 3d 20 .else....plan =
2270: 70 6c 61 6e 5b 31 2e 2e 24 5d 3b 0a 09 7d 0a 7d plan[1..$];..}.}
2280: 0a 0a 2f 2f 61 6c 69 61 73 20 53 6f 6c 76 65 72 ..//alias Solver
2290: 5f 32 21 28 53 6f 6c 76 65 72 5f 31 29 20 4d 61 _2!(Solver_1) Ma
22a0: 69 6e 53 6f 6c 76 65 72 3b 0a 61 6c 69 61 73 20 inSolver;.alias
22b0: 53 6f 6c 76 65 72 5f 31 20 4d 61 69 6e 53 6f 6c Solver_1 MainSol
22c0: 76 65 72 3b 0a 2a 2f 0a ver;.*/.