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 63 6f 6e 73 74 28 47 61 6d 65 29 20 67 29 s(const(Game) g)
0040: 20 7b 7d 0a 09 63 68 61 72 20 73 69 6e 67 6c 65 {}..char single
0050: 5f 73 74 65 70 28 29 20 7b 20 72 65 74 75 72 6e _step() { return
0060: 20 27 57 27 3b 20 7d 0a 7d 0a 0a 63 6c 61 73 73 'W'; }.}..class
0070: 20 53 6f 6c 76 65 72 5f 31 0a 7b 0a 09 69 6e 74 Solver_1.{..int
0080: 20 77 61 69 74 5f 63 6f 75 6e 74 20 3d 20 30 3b wait_count = 0;
0090: 0a 09 69 6e 74 20 63 68 6f 6b 65 5f 63 6f 75 6e ..int choke_coun
00a0: 74 20 3d 20 30 3b 0a 0a 09 47 61 6d 65 20 67 3b t = 0;...Game g;
00b0: 0a 09 74 68 69 73 28 63 6f 6e 73 74 28 47 61 6d ..this(const(Gam
00c0: 65 29 20 67 29 0a 09 7b 0a 09 09 74 68 69 73 2e e) g)..{...this.
00d0: 67 20 3d 20 67 2e 63 6c 6f 6e 65 28 29 3b 0a 09 g = g.clone();..
00e0: 09 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 20 .forbidden_cell
00f0: 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 = new bool[][](g
0100: 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 2e .map.H+2, g.map.
0110: 57 2b 32 29 3b 0a 09 7d 0a 0a 09 63 68 61 72 20 W+2);..}...char
0120: 73 69 6e 67 6c 65 5f 73 74 65 70 28 29 0a 09 7b single_step()..{
0130: 0a 09 09 54 75 70 6c 65 21 28 73 74 72 69 6e 67 ...Tuple!(string
0140: 2c 69 6e 74 29 20 64 65 20 3d 20 64 65 61 74 68 ,int) de = death
0150: 5f 6d 6f 76 65 28 67 29 3b 0a 09 09 63 68 61 72 _move(g);...char
0160: 20 63 20 3d 20 61 63 74 28 67 2c 20 64 65 5b 30 c = act(g, de[0
0170: 5d 2c 20 64 65 5b 31 5d 29 3b 0a 09 09 67 2e 63 ], de[1]);...g.c
0180: 6f 6d 6d 61 6e 64 28 63 29 3b 0a 09 09 72 65 74 ommand(c);...ret
0190: 75 72 6e 20 63 3b 0a 09 7d 0a 0a 09 54 75 70 6c urn c;..}...Tupl
01a0: 65 21 28 73 74 72 69 6e 67 2c 69 6e 74 29 20 64 e!(string,int) d
01b0: 65 61 74 68 5f 6d 6f 76 65 28 63 6f 6e 73 74 28 eath_move(const(
01c0: 47 61 6d 65 29 20 67 29 0a 09 7b 0a 09 09 73 74 Game) g)..{...st
01d0: 72 69 6e 67 20 64 65 61 74 68 3b 0a 09 09 69 6e ring death;...in
01e0: 74 20 63 68 6f 69 63 65 20 3d 20 30 3b 0a 09 09 t choice = 0;...
01f0: 66 6f 72 65 61 63 68 28 63 68 61 72 20 63 3b 20 foreach(char c;
0200: 22 55 44 4c 52 57 22 29 20 7b 0a 09 09 09 47 61 "UDLRW") {....Ga
0210: 6d 65 20 67 67 20 3d 20 67 2e 63 6c 6f 6e 65 28 me gg = g.clone(
0220: 29 3b 0a 09 09 09 67 67 2e 63 6f 6d 6d 61 6e 64 );....gg.command
0230: 28 63 29 3b 0a 09 09 09 69 66 28 20 21 67 67 2e (c);....if( !gg.
0240: 63 6c 65 61 72 65 64 20 26 26 20 67 67 2e 64 65 cleared && gg.de
0250: 61 64 20 29 0a 09 09 09 09 64 65 61 74 68 20 7e ad ).....death ~
0260: 3d 20 63 3b 0a 09 09 09 65 6c 73 65 20 69 66 28 = c;....else if(
0270: 20 67 67 2e 6d 61 70 2e 72 6f 62 6f 74 20 21 3d gg.map.robot !=
0280: 20 67 2e 6d 61 70 2e 72 6f 62 6f 74 20 29 0a 09 g.map.robot )..
0290: 09 09 09 63 68 6f 69 63 65 2b 2b 3b 0a 09 09 09 ...choice++;....
02a0: 65 6c 73 65 20 69 66 28 20 63 20 21 3d 20 27 57 else if( c != 'W
02b0: 27 20 29 20 2f 2f 20 6d 65 61 6e 69 6e 67 6c 65 ' ) // meaningle
02c0: 73 73 20 6d 6f 76 65 0a 09 09 09 09 64 65 61 74 ss move.....deat
02d0: 68 20 7e 3d 20 63 3b 0a 09 09 7d 0a 09 09 72 65 h ~= c;...}...re
02e0: 74 75 72 6e 20 74 75 70 6c 65 28 64 65 61 74 68 turn tuple(death
02f0: 2c 20 63 68 6f 69 63 65 29 3b 0a 09 7d 0a 0a 09 , choice);..}...
0300: 54 75 70 6c 65 21 28 50 6f 73 2c 20 69 6e 74 29 Tuple!(Pos, int)
0310: 5b 5d 20 6c 6f 67 3b 0a 09 62 6f 6f 6c 5b 5d 5b [] log;..bool[][
0320: 5d 20 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c ] forbidden_cell
0330: 3b 0a 0a 09 63 68 61 72 20 61 63 74 28 63 6f 6e ;...char act(con
0340: 73 74 28 47 61 6d 65 29 20 67 2c 20 73 74 72 69 st(Game) g, stri
0350: 6e 67 20 64 65 61 74 68 2c 20 69 6e 74 20 62 72 ng death, int br
0360: 65 61 74 68 29 0a 09 7b 0a 09 09 63 6f 6e 73 74 eath)..{...const
0370: 20 50 6f 73 20 20 20 72 6f 20 3d 20 67 2e 6d 61 Pos ro = g.ma
0380: 70 2e 72 6f 62 6f 74 3b 0a 09 09 63 6f 6e 73 74 p.robot;...const
0390: 20 50 6f 73 5b 5d 20 6c 61 20 3d 20 67 2e 6d 61 Pos[] la = g.ma
03a0: 70 2e 6c 61 6d 62 64 61 73 28 29 3b 0a 09 09 63 p.lambdas();...c
03b0: 6f 6e 73 74 20 50 6f 73 20 20 20 6c 69 20 3d 20 onst Pos li =
03c0: 67 2e 6d 61 70 2e 6c 69 66 74 3b 0a 0a 09 09 54 g.map.lift;....T
03d0: 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b uple!(char,int)[
03e0: 5d 20 63 61 6e 64 3b 0a 09 09 63 68 61 72 20 63 ] cand;...char c
03f0: 20 3d 20 27 57 27 3b 0a 09 09 69 66 28 20 6c 61 = 'W';...if( la
0400: 2e 65 6d 70 74 79 20 29 20 7b 0a 09 09 09 63 61 .empty ) {....ca
0410: 6e 64 20 3d 20 73 65 61 72 63 68 28 67 2c 20 72 nd = search(g, r
0420: 6f 2c 20 5b 6c 69 5d 2c 20 64 65 61 74 68 29 3b o, [li], death);
0430: 0a 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 09 63 ...} else {....c
0440: 61 6e 64 20 7e 3d 20 73 65 61 72 63 68 28 67 2c and ~= search(g,
0450: 20 72 6f 2c 20 6c 61 2c 20 64 65 61 74 68 29 3b ro, la, death);
0460: 0a 09 09 7d 0a 0a 09 09 2f 2f 20 27 64 69 67 27 ...}....// 'dig'
0470: 20 6d 6f 64 65 0a 09 09 69 66 28 63 61 6e 64 2e mode...if(cand.
0480: 65 6d 70 74 79 29 20 7b 0a 09 09 09 63 6f 6e 73 empty) {....cons
0490: 74 28 50 6f 73 29 5b 5d 20 74 67 74 3b 0a 09 09 t(Pos)[] tgt;...
04a0: 09 66 6f 72 28 69 6e 74 20 79 3d 31 3b 20 79 3c .for(int y=1; y<
04b0: 3d 67 2e 6d 61 70 2e 48 3b 20 2b 2b 79 29 0a 09 =g.map.H; ++y)..
04c0: 09 09 66 6f 72 28 69 6e 74 20 78 3d 31 3b 20 78 ..for(int x=1; x
04d0: 3c 3d 67 2e 6d 61 70 2e 57 3b 20 2b 2b 78 29 0a <=g.map.W; ++x).
04e0: 09 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2c 78 ....if(g.map[y,x
04f0: 5d 3d 3d 27 2e 27 29 0a 09 09 09 09 09 69 66 28 ]=='.')......if(
0500: 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 2a g.map[y+1,x]=='*
0510: 27 7c 7c 67 2e 6d 61 70 5b 79 2b 31 2c 78 2d 31 '||g.map[y+1,x-1
0520: 5d 3d 3d 27 2a 27 7c 7c 67 2e 6d 61 70 5b 79 2b ]=='*'||g.map[y+
0530: 31 2c 78 2b 31 5d 3d 3d 27 2a 27 0a 09 09 09 09 1,x+1]=='*'.....
0540: 09 20 7c 7c 67 2e 6d 61 70 5b 79 2c 78 2b 31 5d . ||g.map[y,x+1]
0550: 3d 3d 27 2a 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 =='*'||g.map[y,x
0560: 2d 31 5d 3d 3d 27 2a 27 29 0a 09 09 09 09 09 09 -1]=='*').......
0570: 74 67 74 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 tgt ~= new Pos(y
0580: 2c 78 29 3b 0a 09 09 09 63 61 6e 64 20 7e 3d 20 ,x);....cand ~=
0590: 73 65 61 72 63 68 28 67 2c 20 72 6f 2c 20 74 67 search(g, ro, tg
05a0: 74 2c 20 64 65 61 74 68 2c 20 74 72 75 65 29 3b t, death, true);
05b0: 0a 09 09 7d 0a 0a 09 09 69 66 28 63 61 6e 64 2e ...}....if(cand.
05c0: 65 6d 70 74 79 29 20 7b 0a 09 09 09 63 68 6f 6b empty) {....chok
05d0: 65 5f 63 6f 75 6e 74 2b 2b 3b 0a 09 09 09 63 61 e_count++;....ca
05e0: 6e 64 20 7e 3d 20 74 75 70 6c 65 28 27 57 27 2c nd ~= tuple('W',
05f0: 69 6e 74 2e 6d 61 78 29 3b 0a 09 09 7d 0a 09 09 int.max);...}...
0600: 73 6f 72 74 21 28 28 54 75 70 6c 65 21 28 63 68 sort!((Tuple!(ch
0610: 61 72 2c 69 6e 74 29 20 63 31 2c 20 54 75 70 6c ar,int) c1, Tupl
0620: 65 21 28 63 68 61 72 2c 69 6e 74 29 20 63 32 29 e!(char,int) c2)
0630: 7b 0a 09 09 09 69 66 28 63 31 5b 31 5d 20 21 3d {....if(c1[1] !=
0640: 20 63 32 5b 31 5d 29 0a 09 09 09 09 72 65 74 75 c2[1]).....retu
0650: 72 6e 20 63 31 5b 31 5d 20 3c 20 63 32 5b 31 5d rn c1[1] < c2[1]
0660: 3b 0a 09 09 09 72 65 74 75 72 6e 20 63 31 5b 30 ;....return c1[0
0670: 5d 20 3c 20 63 32 5b 30 5d 3b 0a 09 09 7d 29 28 ] < c2[0];...})(
0680: 63 61 6e 64 29 3b 0a 09 09 63 20 3d 20 63 61 6e cand);...c = can
0690: 64 5b 30 5d 5b 30 5d 3b 0a 0a 09 09 69 66 28 64 d[0][0];....if(d
06a0: 65 61 74 68 2e 63 6f 75 6e 74 28 63 29 20 7c 7c eath.count(c) ||
06b0: 20 77 61 69 74 5f 63 6f 75 6e 74 3e 3d 32 29 20 wait_count>=2)
06c0: 7b 0a 09 09 09 66 6f 72 65 61 63 68 28 63 68 61 {....foreach(cha
06d0: 72 20 6c 69 76 65 3b 20 22 55 44 4c 52 57 22 29 r live; "UDLRW")
06e0: 0a 09 09 09 09 69 66 28 64 65 61 74 68 2e 63 6f .....if(death.co
06f0: 75 6e 74 28 6c 69 76 65 29 3d 3d 30 29 20 7b 0a unt(live)==0) {.
0700: 09 09 09 09 09 63 3d 6c 69 76 65 3b 0a 09 09 09 .....c=live;....
0710: 09 09 62 72 65 61 6b 3b 0a 09 09 09 09 7d 0a 09 ..break;.....}..
0720: 09 7d 0a 0a 09 09 69 66 28 63 20 3d 3d 20 27 57 .}....if(c == 'W
0730: 27 29 0a 09 09 09 77 61 69 74 5f 63 6f 75 6e 74 ')....wait_count
0740: 2b 2b 3b 0a 09 09 65 6c 73 65 0a 09 09 09 77 61 ++;...else....wa
0750: 69 74 5f 63 6f 75 6e 74 20 3d 20 30 3b 0a 09 09 it_count = 0;...
0760: 69 66 28 63 68 6f 6b 65 5f 63 6f 75 6e 74 20 3e if(choke_count >
0770: 3d 20 67 2e 6d 61 70 2e 48 29 0a 09 09 09 63 20 = g.map.H)....c
0780: 3d 20 27 41 27 3b 0a 0a 09 09 62 6f 6f 6c 5b 63 = 'A';....bool[c
0790: 68 61 72 5d 20 63 68 6f 69 63 65 3b 0a 09 09 66 har] choice;...f
07a0: 6f 72 65 61 63 68 28 74 3b 20 63 61 6e 64 29 0a oreach(t; cand).
07b0: 09 09 09 63 68 6f 69 63 65 5b 74 5b 30 5d 5d 20 ...choice[t[0]]
07c0: 3d 20 74 72 75 65 3b 0a 09 09 6c 6f 67 20 7e 3d = true;...log ~=
07d0: 20 74 75 70 6c 65 28 72 6f 2e 63 6c 6f 6e 65 28 tuple(ro.clone(
07e0: 29 2c 20 63 61 73 74 28 69 6e 74 29 63 68 6f 69 ), cast(int)choi
07f0: 63 65 2e 6c 65 6e 67 74 68 29 3b 0a 09 09 69 66 ce.length);...if
0800: 28 6c 6f 67 2e 6c 65 6e 67 74 68 20 3e 20 35 29 (log.length > 5)
0810: 0a 09 09 09 6c 6f 67 20 3d 20 6c 6f 67 5b 24 2d ....log = log[$-
0820: 35 2e 2e 24 5d 3b 0a 09 09 69 6e 74 20 63 6e 74 5..$];...int cnt
0830: 20 3d 20 30 3b 0a 09 09 66 6f 72 65 61 63 68 28 = 0;...foreach(
0840: 6c 3b 20 6c 6f 67 29 0a 09 09 09 69 66 28 6c 5b l; log)....if(l[
0850: 30 5d 20 3d 3d 20 6c 6f 67 5b 24 2d 31 5d 5b 30 0] == log[$-1][0
0860: 5d 29 0a 09 09 09 09 2b 2b 63 6e 74 3b 0a 09 09 ]).....++cnt;...
0870: 69 66 28 20 63 6e 74 20 3e 3d 20 33 20 26 26 20 if( cnt >= 3 &&
0880: 62 72 65 61 74 68 3d 3d 31 20 29 20 7b 0a 09 09 breath==1 ) {...
0890: 09 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 5b .forbidden_cell[
08a0: 72 6f 2e 79 5d 5b 72 6f 2e 78 5d 20 3d 20 74 72 ro.y][ro.x] = tr
08b0: 75 65 3b 0a 09 09 7d 0a 0a 09 09 72 65 74 75 72 ue;...}....retur
08c0: 6e 20 63 3b 0a 09 7d 0a 0a 09 54 75 70 6c 65 21 n c;..}...Tuple!
08d0: 28 63 68 61 72 2c 69 6e 74 29 5b 5d 20 73 65 61 (char,int)[] sea
08e0: 72 63 68 28 69 6e 20 47 61 6d 65 20 67 2c 20 69 rch(in Game g, i
08f0: 6e 20 50 6f 73 20 73 2c 20 69 6e 20 50 6f 73 5b n Pos s, in Pos[
0900: 5d 20 67 73 2c 20 73 74 72 69 6e 67 20 64 65 61 ] gs, string dea
0910: 74 68 2c 20 62 6f 6f 6c 20 64 61 6e 67 65 72 5f th, bool danger_
0920: 6f 6b 3d 66 61 6c 73 65 29 0a 09 7b 0a 09 09 62 ok=false)..{...b
0930: 6f 6f 6c 20 64 61 6e 67 65 72 28 69 6e 74 20 79 ool danger(int y
0940: 2c 20 69 6e 74 20 78 29 0a 09 09 7b 0a 09 09 09 , int x)...{....
0950: 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 20 3d 3d if(g.map[y,x] ==
0960: 20 27 20 27 20 7c 7c 20 67 2e 6d 61 70 5b 79 2c ' ' || g.map[y,
0970: 78 5d 20 3d 3d 20 27 52 27 29 0a 09 09 09 09 72 x] == 'R').....r
0980: 65 74 75 72 6e 20 66 61 6c 73 65 3b 0a 09 09 09 eturn false;....
0990: 69 66 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 20 if(g.map[y+1,x]
09a0: 3d 3d 20 27 2a 27 29 0a 09 09 09 09 72 65 74 75 == '*').....retu
09b0: 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 28 67 rn true;....if(g
09c0: 2e 6d 61 70 5b 79 2b 31 2c 78 2d 31 5d 3d 3d 27 .map[y+1,x-1]=='
09d0: 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 2c 78 *' && (g.map[y,x
09e0: 2d 31 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 -1]=='\\'||g.map
09f0: 5b 79 2c 78 2d 31 5d 3d 3d 27 2a 27 29 20 26 26 [y,x-1]=='*') &&
0a00: 20 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d (g.map[y+1,x]==
0a10: 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2b 31 2c 78 ' '||g.map[y+1,x
0a20: 5d 3d 3d 27 52 27 29 29 0a 09 09 09 09 72 65 74 ]=='R')).....ret
0a30: 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 28 urn true;....if(
0a40: 67 2e 6d 61 70 5b 79 2b 31 2c 78 2b 31 5d 3d 3d g.map[y+1,x+1]==
0a50: 27 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 2c '*' && (g.map[y,
0a60: 78 2b 31 5d 3d 3d 27 2a 27 29 20 26 26 20 28 67 x+1]=='*') && (g
0a70: 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 20 27 .map[y+1,x]==' '
0a80: 7c 7c 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d ||g.map[y+1,x]==
0a90: 27 52 27 29 29 0a 09 09 09 09 72 65 74 75 72 6e 'R')).....return
0aa0: 20 74 72 75 65 3b 0a 09 09 09 69 66 28 67 2e 6d true;....if(g.m
0ab0: 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27 2a 27 20 26 ap[y,x-1]=='*' &
0ac0: 26 20 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 2d 31 & (g.map[y-1,x-1
0ad0: 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 ]=='\\'||g.map[y
0ae0: 2d 31 2c 78 2d 31 5d 3d 3d 27 2a 27 29 20 26 26 -1,x-1]=='*') &&
0af0: 20 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d (g.map[y-1,x]==
0b00: 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2d 31 2c 78 ' '||g.map[y-1,x
0b10: 5d 3d 3d 27 52 27 29 29 0a 09 09 09 09 72 65 74 ]=='R')).....ret
0b20: 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 28 urn true;....if(
0b30: 67 2e 6d 61 70 5b 79 2c 78 2b 31 5d 3d 3d 27 2a g.map[y,x+1]=='*
0b40: 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 2d 31 2c ' && (g.map[y-1,
0b50: 78 2b 31 5d 3d 3d 27 2a 27 29 20 26 26 20 28 67 x+1]=='*') && (g
0b60: 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 20 27 .map[y-1,x]==' '
0b70: 7c 7c 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d ||g.map[y-1,x]==
0b80: 27 52 27 29 29 0a 09 09 09 09 72 65 74 75 72 6e 'R')).....return
0b90: 20 74 72 75 65 3b 0a 09 09 09 72 65 74 75 72 6e true;....return
0ba0: 20 66 61 6c 73 65 3b 0a 09 09 7d 0a 0a 09 09 2f false;...}..../
0bb0: 2f 20 61 76 6f 69 64 20 64 69 72 65 63 74 6c 79 / avoid directly
0bc0: 20 62 65 6c 6f 77 20 27 2a 27 0a 09 09 54 75 70 below '*'...Tup
0bd0: 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d 20 le!(char,int)[]
0be0: 74 72 79 41 28 29 20 7b 0a 09 09 09 63 6f 6e 73 tryA() {....cons
0bf0: 74 28 50 6f 73 29 5b 5d 20 71 3b 0a 09 09 09 66 t(Pos)[] q;....f
0c00: 6f 72 65 61 63 68 28 70 3b 20 67 73 29 0a 09 09 oreach(p; gs)...
0c10: 09 09 69 66 28 21 64 61 6e 67 65 72 28 70 2e 79 ..if(!danger(p.y
0c20: 2c 70 2e 78 29 29 0a 09 09 09 09 09 71 20 7e 3d ,p.x))......q ~=
0c30: 20 70 3b 0a 09 09 09 62 6f 6f 6c 5b 5d 5b 5d 20 p;....bool[][]
0c40: 76 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d v = new bool[][]
0c50: 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 (g.map.H+2, g.ma
0c60: 70 2e 57 2b 32 29 3b 0a 09 09 09 66 6f 72 65 61 p.W+2);....forea
0c70: 63 68 28 70 3b 20 71 29 20 76 5b 70 2e 79 5d 5b ch(p; q) v[p.y][
0c80: 70 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 09 66 6f p.x]=true;....fo
0c90: 72 28 69 6e 74 20 73 74 65 70 3d 31 3b 20 71 2e r(int step=1; q.
0ca0: 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 29 20 length; ++step)
0cb0: 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a {.....Pos[] q2;.
0cc0: 09 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 ....foreach(p; q
0cd0: 29 20 7b 0a 09 09 09 09 09 69 6e 74 5b 5d 20 79 ) {......int[] y
0ce0: 79 79 3d 5b 70 2e 79 2d 31 2c 70 2e 79 2b 31 2c yy=[p.y-1,p.y+1,
0cf0: 70 2e 79 2c 70 2e 79 5d 3b 0a 09 09 09 09 09 69 p.y,p.y];......i
0d00: 6e 74 5b 5d 20 78 78 78 3d 5b 70 2e 78 2c 70 2e nt[] xxx=[p.x,p.
0d10: 78 2c 70 2e 78 2d 31 2c 70 2e 78 2b 31 5d 3b 0a x,p.x-1,p.x+1];.
0d20: 09 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 .....for(int i=0
0d30: 3b 20 69 3c 79 79 79 2e 6c 65 6e 67 74 68 3b 20 ; i<yyy.length;
0d40: 2b 2b 69 29 20 7b 0a 09 09 09 09 09 09 69 6e 74 ++i) {.......int
0d50: 20 79 20 3d 20 79 79 79 5b 69 5d 3b 0a 09 09 09 y = yyy[i];....
0d60: 09 09 09 69 6e 74 20 78 20 3d 20 78 78 78 5b 69 ...int x = xxx[i
0d70: 5d 3b 0a 09 09 09 09 09 09 69 66 28 27 31 27 3c ];.......if('1'<
0d80: 3d 67 2e 6d 61 70 5b 79 2c 78 5d 26 26 67 2e 6d =g.map[y,x]&&g.m
0d90: 61 70 5b 79 2c 78 5d 3c 3d 27 39 27 29 20 7b 0a ap[y,x]<='9') {.
0da0: 09 09 09 09 09 09 09 66 6f 72 65 61 63 68 28 70 .......foreach(p
0db0: 70 70 3b 20 67 2e 6d 61 70 2e 74 72 5f 73 6f 75 pp; g.map.tr_sou
0dc0: 72 63 65 5b 67 2e 6d 61 70 5b 79 2c 78 5d 5d 29 rce[g.map[y,x]])
0dd0: 20 7b 0a 09 09 09 09 09 09 09 09 79 79 79 20 7e {.........yyy ~
0de0: 3d 20 70 70 70 2e 79 3b 0a 09 09 09 09 09 09 09 = ppp.y;........
0df0: 09 78 78 78 20 7e 3d 20 70 70 70 2e 78 3b 0a 09 .xxx ~= ppp.x;..
0e00: 09 09 09 09 09 09 7d 0a 09 09 09 09 09 09 09 63 ......}........c
0e10: 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 7d ontinue;.......}
0e20: 0a 09 09 09 09 09 09 69 66 28 76 5b 79 5d 5b 78 .......if(v[y][x
0e30: 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 ]) continue;....
0e40: 09 09 09 69 66 28 79 3d 3d 73 2e 79 20 26 26 20 ...if(y==s.y &&
0e50: 78 3d 3d 73 2e 78 20 26 26 20 69 3c 34 29 20 7b x==s.x && i<4) {
0e60: 0a 09 09 09 09 09 09 09 63 68 61 72 20 63 20 3d ........char c =
0e70: 20 22 55 44 52 4c 22 5b 69 5d 3b 0a 09 09 09 09 "UDRL"[i];.....
0e80: 09 09 09 69 66 28 20 64 65 61 74 68 2e 63 6f 75 ...if( death.cou
0e90: 6e 74 28 63 29 20 3d 3d 20 30 20 29 0a 09 09 09 nt(c) == 0 )....
0ea0: 09 09 09 09 09 72 65 74 75 72 6e 20 5b 74 75 70 .....return [tup
0eb0: 6c 65 28 63 2c 73 74 65 70 29 5d 3b 0a 09 09 09 le(c,step)];....
0ec0: 09 09 09 7d 20 65 6c 73 65 20 69 66 28 66 6f 72 ...} else if(for
0ed0: 62 69 64 64 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 bidden_cell[y][x
0ee0: 5d 29 7b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 ]){.......} else
0ef0: 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d if(g.map[y,x]==
0f00: 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d ' '||g.map[y,x]=
0f10: 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 ='\\'||g.map[y,x
0f20: 5d 3d 3d 27 2e 27 7c 7c 69 3e 3d 34 29 20 7b 0a ]=='.'||i>=4) {.
0f30: 09 09 09 09 09 09 09 69 66 28 64 61 6e 67 65 72 .......if(danger
0f40: 28 79 2c 78 29 29 0a 09 09 09 09 09 09 09 09 63 (y,x)).........c
0f50: 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 09 ontinue;........
0f60: 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c q2 ~= new Pos(y,
0f70: 78 29 3b 0a 09 09 09 09 09 09 09 76 5b 79 5d 5b x);........v[y][
0f80: 78 5d 3d 74 72 75 65 3b 0a 09 09 09 09 09 09 7d x]=true;.......}
0f90: 0a 09 09 09 09 09 7d 0a 09 09 09 09 7d 0a 09 09 ......}.....}...
0fa0: 09 09 71 20 3d 20 71 32 3b 0a 09 09 09 7d 0a 09 ..q = q2;....}..
0fb0: 09 09 72 65 74 75 72 6e 20 5b 5d 3b 0a 09 09 7d ..return [];...}
0fc0: 0a 0a 09 09 2f 2f 20 61 6e 79 20 65 6d 70 74 79 ....// any empty
0fd0: 20 73 70 61 63 65 20 69 73 20 6d 79 20 67 72 6f space is my gro
0fe0: 75 6e 64 0a 09 09 54 75 70 6c 65 21 28 63 68 61 und...Tuple!(cha
0ff0: 72 2c 69 6e 74 29 5b 5d 20 74 72 79 42 28 29 20 r,int)[] tryB()
1000: 7b 0a 09 09 09 63 6f 6e 73 74 28 50 6f 73 29 5b {....const(Pos)[
1010: 5d 20 71 3b 0a 09 09 09 66 6f 72 65 61 63 68 28 ] q;....foreach(
1020: 70 3b 20 67 73 29 20 71 20 7e 3d 20 70 3b 0a 09 p; gs) q ~= p;..
1030: 09 09 62 6f 6f 6c 5b 5d 5b 5d 20 76 20 3d 20 6e ..bool[][] v = n
1040: 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 ew bool[][](g.ma
1050: 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 p.H+2, g.map.W+2
1060: 29 3b 0a 09 09 09 66 6f 72 65 61 63 68 28 70 3b );....foreach(p;
1070: 20 71 29 20 76 5b 70 2e 79 5d 5b 70 2e 78 5d 3d q) v[p.y][p.x]=
1080: 74 72 75 65 3b 0a 09 09 09 66 6f 72 28 69 6e 74 true;....for(int
1090: 20 73 74 65 70 3d 31 30 3b 20 71 2e 6c 65 6e 67 step=10; q.leng
10a0: 74 68 3b 20 2b 2b 73 74 65 70 29 20 7b 0a 09 09 th; ++step) {...
10b0: 09 09 50 6f 73 5b 5d 20 71 32 3b 0a 09 09 09 09 ..Pos[] q2;.....
10c0: 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 7b 0a foreach(p; q) {.
10d0: 09 09 09 09 09 69 6e 74 5b 5d 20 79 79 79 3d 5b .....int[] yyy=[
10e0: 70 2e 79 2d 31 2c 70 2e 79 2b 31 2c 70 2e 79 2c p.y-1,p.y+1,p.y,
10f0: 70 2e 79 5d 3b 0a 09 09 09 09 09 69 6e 74 5b 5d p.y];......int[]
1100: 20 78 78 78 3d 5b 70 2e 78 2c 70 2e 78 2c 70 2e xxx=[p.x,p.x,p.
1110: 78 2d 31 2c 70 2e 78 2b 31 5d 3b 0a 09 09 09 09 x-1,p.x+1];.....
1120: 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c .for(int i=0; i<
1130: 79 79 79 2e 6c 65 6e 67 74 68 3b 20 2b 2b 69 29 yyy.length; ++i)
1140: 20 7b 0a 09 09 09 09 09 09 69 6e 74 20 79 20 3d {.......int y =
1150: 20 79 79 79 5b 69 5d 3b 0a 09 09 09 09 09 09 69 yyy[i];.......i
1160: 6e 74 20 78 20 3d 20 78 78 78 5b 69 5d 3b 0a 09 nt x = xxx[i];..
1170: 09 09 09 09 09 69 66 28 27 31 27 3c 3d 67 2e 6d .....if('1'<=g.m
1180: 61 70 5b 79 2c 78 5d 26 26 67 2e 6d 61 70 5b 79 ap[y,x]&&g.map[y
1190: 2c 78 5d 3c 3d 27 39 27 29 20 7b 0a 09 09 09 09 ,x]<='9') {.....
11a0: 09 09 09 66 6f 72 65 61 63 68 28 70 70 70 3b 20 ...foreach(ppp;
11b0: 67 2e 6d 61 70 2e 74 72 5f 73 6f 75 72 63 65 5b g.map.tr_source[
11c0: 67 2e 6d 61 70 5b 79 2c 78 5d 5d 29 20 7b 0a 09 g.map[y,x]]) {..
11d0: 09 09 09 09 09 09 09 79 79 79 20 7e 3d 20 70 70 .......yyy ~= pp
11e0: 70 2e 79 3b 0a 09 09 09 09 09 09 09 09 78 78 78 p.y;.........xxx
11f0: 20 7e 3d 20 70 70 70 2e 78 3b 0a 09 09 09 09 09 ~= ppp.x;......
1200: 09 09 7d 0a 09 09 09 09 09 09 09 63 6f 6e 74 69 ..}........conti
1210: 6e 75 65 3b 0a 09 09 09 09 09 09 7d 0a 09 09 09 nue;.......}....
1220: 09 09 09 69 66 28 76 5b 79 5d 5b 78 5d 29 20 63 ...if(v[y][x]) c
1230: 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 69 ontinue;.......i
1240: 66 28 79 3d 3d 73 2e 79 20 26 26 20 78 3d 3d 73 f(y==s.y && x==s
1250: 2e 78 20 26 26 20 69 3c 34 29 20 7b 0a 09 09 09 .x && i<4) {....
1260: 09 09 09 09 63 68 61 72 20 63 20 3d 20 22 55 44 ....char c = "UD
1270: 52 4c 22 5b 69 5d 3b 0a 09 09 09 09 09 09 09 69 RL"[i];........i
1280: 66 28 20 64 65 61 74 68 2e 63 6f 75 6e 74 28 63 f( death.count(c
1290: 29 20 3d 3d 20 30 20 29 0a 09 09 09 09 09 09 09 ) == 0 )........
12a0: 09 72 65 74 75 72 6e 20 5b 74 75 70 6c 65 28 63 .return [tuple(c
12b0: 2c 73 74 65 70 29 5d 3b 0a 09 09 09 09 09 09 7d ,step)];.......}
12c0: 20 65 6c 73 65 20 69 66 28 66 6f 72 62 69 64 64 else if(forbidd
12d0: 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 5d 29 7b 0a en_cell[y][x]){.
12e0: 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 ......} else if(
12f0: 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c g.map[y,x]==' '|
1300: 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c |g.map[y,x]=='\\
1310: 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 '||g.map[y,x]=='
1320: 2e 27 7c 7c 69 3e 3d 34 29 20 7b 0a 09 09 09 09 .'||i>=4) {.....
1330: 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73 ...q2 ~= new Pos
1340: 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 09 76 5b (y,x);........v[
1350: 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09 09 y][x]=true;.....
1360: 09 09 7d 0a 09 09 09 09 09 7d 0a 09 09 09 09 7d ..}......}.....}
1370: 0a 09 09 09 09 71 20 3d 20 71 32 3b 0a 09 09 09 .....q = q2;....
1380: 7d 0a 09 09 09 72 65 74 75 72 6e 20 5b 5d 3b 0a }....return [];.
1390: 09 09 7d 0a 0a 09 09 2f 2f 20 70 75 73 68 20 72 ..}....// push r
13a0: 6f 63 6b 73 21 0a 09 09 54 75 70 6c 65 21 28 63 ocks!...Tuple!(c
13b0: 68 61 72 2c 69 6e 74 29 5b 5d 20 74 72 79 43 28 har,int)[] tryC(
13c0: 29 20 7b 0a 09 09 09 63 6f 6e 73 74 28 50 6f 73 ) {....const(Pos
13d0: 29 5b 5d 20 71 3b 0a 09 09 09 66 6f 72 65 61 63 )[] q;....foreac
13e0: 68 28 70 3b 20 67 73 29 20 71 20 7e 3d 20 70 3b h(p; gs) q ~= p;
13f0: 0a 09 09 09 62 6f 6f 6c 5b 5d 5b 5d 20 76 20 3d ....bool[][] v =
1400: 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e new bool[][](g.
1410: 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 2e 57 map.H+2, g.map.W
1420: 2b 32 29 3b 0a 09 09 09 66 6f 72 65 61 63 68 28 +2);....foreach(
1430: 70 3b 20 71 29 20 76 5b 70 2e 79 5d 5b 70 2e 78 p; q) v[p.y][p.x
1440: 5d 3d 74 72 75 65 3b 0a 09 09 09 66 6f 72 28 69 ]=true;....for(i
1450: 6e 74 20 73 74 65 70 3d 32 30 3b 20 71 2e 6c 65 nt step=20; q.le
1460: 6e 67 74 68 3b 20 2b 2b 73 74 65 70 29 20 7b 0a ngth; ++step) {.
1470: 09 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a 09 09 ....Pos[] q2;...
1480: 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 ..foreach(p; q)
1490: 7b 0a 09 09 09 09 09 69 6e 74 5b 5d 20 79 79 79 {......int[] yyy
14a0: 3d 5b 70 2e 79 2d 31 2c 70 2e 79 2b 31 2c 70 2e =[p.y-1,p.y+1,p.
14b0: 79 2c 70 2e 79 5d 3b 0a 09 09 09 09 09 69 6e 74 y,p.y];......int
14c0: 5b 5d 20 78 78 78 3d 5b 70 2e 78 2c 70 2e 78 2c [] xxx=[p.x,p.x,
14d0: 70 2e 78 2d 31 2c 70 2e 78 2b 31 5d 3b 0a 09 09 p.x-1,p.x+1];...
14e0: 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
14f0: 69 3c 79 79 79 2e 6c 65 6e 67 74 68 3b 20 2b 2b i<yyy.length; ++
1500: 69 29 20 7b 0a 09 09 09 09 09 09 69 6e 74 20 79 i) {.......int y
1510: 20 3d 20 79 79 79 5b 69 5d 3b 0a 09 09 09 09 09 = yyy[i];......
1520: 09 69 6e 74 20 78 20 3d 20 78 78 78 5b 69 5d 3b .int x = xxx[i];
1530: 0a 09 09 09 09 09 09 69 66 28 27 31 27 3c 3d 67 .......if('1'<=g
1540: 2e 6d 61 70 5b 79 2c 78 5d 26 26 67 2e 6d 61 70 .map[y,x]&&g.map
1550: 5b 79 2c 78 5d 3c 3d 27 39 27 29 20 7b 0a 09 09 [y,x]<='9') {...
1560: 09 09 09 09 09 66 6f 72 65 61 63 68 28 70 70 70 .....foreach(ppp
1570: 3b 20 67 2e 6d 61 70 2e 74 72 5f 73 6f 75 72 63 ; g.map.tr_sourc
1580: 65 5b 67 2e 6d 61 70 5b 79 2c 78 5d 5d 29 20 7b e[g.map[y,x]]) {
1590: 0a 09 09 09 09 09 09 09 09 79 79 79 20 7e 3d 20 .........yyy ~=
15a0: 70 70 70 2e 79 3b 0a 09 09 09 09 09 09 09 09 78 ppp.y;.........x
15b0: 78 78 20 7e 3d 20 70 70 70 2e 78 3b 0a 09 09 09 xx ~= ppp.x;....
15c0: 09 09 09 09 7d 0a 09 09 09 09 09 09 09 63 6f 6e ....}........con
15d0: 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 7d 0a 09 tinue;.......}..
15e0: 09 09 09 09 09 69 66 28 76 5b 79 5d 5b 78 5d 29 .....if(v[y][x])
15f0: 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 continue;......
1600: 09 69 66 28 79 3d 3d 73 2e 79 20 26 26 20 78 3d .if(y==s.y && x=
1610: 3d 73 2e 78 20 26 26 20 69 3c 34 29 20 7b 0a 09 =s.x && i<4) {..
1620: 09 09 09 09 09 09 63 68 61 72 20 63 20 3d 20 22 ......char c = "
1630: 55 44 52 4c 22 5b 69 5d 3b 0a 09 09 09 09 09 09 UDRL"[i];.......
1640: 09 69 66 28 20 64 65 61 74 68 2e 63 6f 75 6e 74 .if( death.count
1650: 28 63 29 20 3d 3d 20 30 20 29 0a 09 09 09 09 09 (c) == 0 )......
1660: 09 09 09 72 65 74 75 72 6e 20 5b 74 75 70 6c 65 ...return [tuple
1670: 28 63 2c 73 74 65 70 29 5d 3b 0a 09 09 09 09 09 (c,step)];......
1680: 09 7d 20 65 6c 73 65 20 69 66 28 66 6f 72 62 69 .} else if(forbi
1690: 64 64 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 5d 29 dden_cell[y][x])
16a0: 7b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 {.......} else i
16b0: 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 f(g.map[y,x]=='
16c0: 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 '||g.map[y,x]=='
16d0: 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d \\'||g.map[y,x]=
16e0: 3d 27 2e 27 7c 7c 69 3e 3d 34 29 20 7b 0a 09 09 ='.'||i>=4) {...
16f0: 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 50 .....q2 ~= new P
1700: 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 09 os(y,x);........
1710: 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 v[y][x]=true;...
1720: 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 69 3c ....} else if(i<
1730: 34 20 26 26 20 28 79 2d 70 2e 79 29 3d 3d 30 20 4 && (y-p.y)==0
1740: 26 26 20 67 2e 6d 61 70 5b 70 5d 3d 3d 27 20 27 && g.map[p]==' '
1750: 20 26 26 20 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d && g.map[y,x]==
1760: 27 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 2b '*' && (g.map[y+
1770: 28 79 2d 70 2e 79 29 2c 78 2b 28 78 2d 70 2e 78 (y-p.y),x+(x-p.x
1780: 29 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 )]==' '||g.map[y
1790: 2b 28 79 2d 70 2e 79 29 2c 78 2b 28 78 2d 70 2e +(y-p.y),x+(x-p.
17a0: 78 29 5d 3d 3d 27 52 27 29 29 20 7b 0a 09 09 09 x)]=='R')) {....
17b0: 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 50 6f ....q2 ~= new Po
17c0: 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 09 76 s(y,x);........v
17d0: 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09 [y][x]=true;....
17e0: 09 09 09 7d 0a 09 09 09 09 09 7d 0a 09 09 09 09 ...}......}.....
17f0: 7d 0a 09 09 09 09 71 20 3d 20 71 32 3b 0a 09 09 }.....q = q2;...
1800: 09 7d 0a 09 09 09 72 65 74 75 72 6e 20 5b 5d 3b .}....return [];
1810: 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e 20 28 64 ...}...return (d
1820: 61 6e 67 65 72 5f 6f 6b 20 3f 20 5b 5d 20 3a 20 anger_ok ? [] :
1830: 74 72 79 41 28 29 29 20 7e 20 74 72 79 42 28 29 tryA()) ~ tryB()
1840: 20 7e 20 74 72 79 43 28 29 3b 0a 09 7d 0a 7d 0a ~ tryC();..}.}.
1850: 0a 61 6c 69 61 73 20 53 6f 6c 76 65 72 5f 31 20 .alias Solver_1
1860: 4d 61 69 6e 53 6f 6c 76 65 72 3b 0a MainSolver;.