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 67 5f 77 63 20 3d 20 30 3b 0a 0a 09 47 61 6d g_wc = 0;...Gam
0090: 65 20 67 3b 0a 09 74 68 69 73 28 63 6f 6e 73 74 e g;..this(const
00a0: 28 47 61 6d 65 29 20 67 29 0a 09 7b 0a 09 09 74 (Game) g)..{...t
00b0: 68 69 73 2e 67 20 3d 20 67 2e 63 6c 6f 6e 65 28 his.g = g.clone(
00c0: 29 3b 0a 09 09 66 6f 72 62 69 64 64 65 6e 5f 63 );...forbidden_c
00d0: 65 6c 6c 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d ell = new bool[]
00e0: 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e [](g.map.H+2, g.
00f0: 6d 61 70 2e 57 2b 32 29 3b 0a 09 7d 0a 0a 09 63 map.W+2);..}...c
0100: 68 61 72 20 73 69 6e 67 6c 65 5f 73 74 65 70 28 har single_step(
0110: 29 0a 09 7b 0a 09 09 54 75 70 6c 65 21 28 73 74 )..{...Tuple!(st
0120: 72 69 6e 67 2c 69 6e 74 29 20 64 65 20 3d 20 64 ring,int) de = d
0130: 65 61 74 68 5f 6d 6f 76 65 28 67 29 3b 0a 09 09 eath_move(g);...
0140: 63 68 61 72 20 63 20 3d 20 61 63 74 28 67 2c 20 char c = act(g,
0150: 64 65 5b 30 5d 2c 20 64 65 5b 31 5d 29 3b 0a 09 de[0], de[1]);..
0160: 09 67 2e 63 6f 6d 6d 61 6e 64 28 63 29 3b 0a 09 .g.command(c);..
0170: 09 72 65 74 75 72 6e 20 63 3b 0a 09 7d 0a 0a 09 .return c;..}...
0180: 54 75 70 6c 65 21 28 73 74 72 69 6e 67 2c 69 6e Tuple!(string,in
0190: 74 29 20 64 65 61 74 68 5f 6d 6f 76 65 28 63 6f t) death_move(co
01a0: 6e 73 74 28 47 61 6d 65 29 20 67 29 0a 09 7b 0a nst(Game) g)..{.
01b0: 09 09 73 74 72 69 6e 67 20 64 65 61 74 68 3b 0a ..string death;.
01c0: 09 09 69 6e 74 20 63 68 6f 69 63 65 20 3d 20 30 ..int choice = 0
01d0: 3b 0a 09 09 66 6f 72 65 61 63 68 28 63 68 61 72 ;...foreach(char
01e0: 20 63 3b 20 22 55 44 4c 52 57 22 29 20 7b 0a 09 c; "UDLRW") {..
01f0: 09 09 47 61 6d 65 20 67 67 20 3d 20 67 2e 63 6c ..Game gg = g.cl
0200: 6f 6e 65 28 29 3b 0a 09 09 09 67 67 2e 63 6f 6d one();....gg.com
0210: 6d 61 6e 64 28 63 29 3b 0a 09 09 09 69 66 28 20 mand(c);....if(
0220: 21 67 67 2e 63 6c 65 61 72 65 64 20 26 26 20 67 !gg.cleared && g
0230: 67 2e 64 65 61 64 20 29 0a 09 09 09 09 64 65 61 g.dead ).....dea
0240: 74 68 20 7e 3d 20 63 3b 0a 09 09 09 65 6c 73 65 th ~= c;....else
0250: 20 69 66 28 20 67 67 2e 6d 61 70 2e 72 6f 62 6f if( gg.map.robo
0260: 74 20 21 3d 20 67 2e 6d 61 70 2e 72 6f 62 6f 74 t != g.map.robot
0270: 20 29 0a 09 09 09 09 63 68 6f 69 63 65 2b 2b 3b ).....choice++;
0280: 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e 20 74 75 ...}...return tu
0290: 70 6c 65 28 64 65 61 74 68 2c 20 63 68 6f 69 63 ple(death, choic
02a0: 65 29 3b 0a 09 7d 0a 0a 09 54 75 70 6c 65 21 28 e);..}...Tuple!(
02b0: 50 6f 73 2c 20 69 6e 74 29 5b 5d 20 6c 6f 67 3b Pos, int)[] log;
02c0: 0a 09 62 6f 6f 6c 5b 5d 5b 5d 20 66 6f 72 62 69 ..bool[][] forbi
02d0: 64 64 65 6e 5f 63 65 6c 6c 3b 0a 0a 09 63 68 61 dden_cell;...cha
02e0: 72 20 61 63 74 28 63 6f 6e 73 74 28 47 61 6d 65 r act(const(Game
02f0: 29 20 67 2c 20 73 74 72 69 6e 67 20 64 65 61 74 ) g, string deat
0300: 68 2c 20 69 6e 74 20 62 72 65 61 74 68 29 0a 09 h, int breath)..
0310: 7b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 20 20 20 {...const Pos
0320: 72 6f 20 3d 20 67 2e 6d 61 70 2e 72 6f 62 6f 74 ro = g.map.robot
0330: 3b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 5b 5d 20 ;...const Pos[]
0340: 6c 61 20 3d 20 67 2e 6d 61 70 2e 6c 61 6d 62 64 la = g.map.lambd
0350: 61 73 28 29 3b 0a 09 09 63 6f 6e 73 74 20 50 6f as();...const Po
0360: 73 20 20 20 6c 69 20 3d 20 67 2e 6d 61 70 2e 6c s li = g.map.l
0370: 69 66 74 3b 0a 0a 09 09 54 75 70 6c 65 21 28 63 ift;....Tuple!(c
0380: 68 61 72 2c 69 6e 74 29 5b 5d 20 63 61 6e 64 3b har,int)[] cand;
0390: 0a 09 09 63 68 61 72 20 63 20 3d 20 27 57 27 3b ...char c = 'W';
03a0: 0a 09 09 69 66 28 20 6c 61 2e 65 6d 70 74 79 20 ...if( la.empty
03b0: 29 20 7b 0a 09 09 09 63 61 6e 64 20 3d 20 73 65 ) {....cand = se
03c0: 61 72 63 68 28 67 2c 20 72 6f 2c 20 6c 69 2c 20 arch(g, ro, li,
03d0: 64 65 61 74 68 29 3b 0a 09 09 7d 20 65 6c 73 65 death);...} else
03e0: 20 7b 0a 09 09 09 66 6f 72 65 61 63 68 28 6c 61 {....foreach(la
03f0: 6d 3b 20 6c 61 29 0a 09 09 09 09 63 61 6e 64 20 m; la).....cand
0400: 7e 3d 20 73 65 61 72 63 68 28 67 2c 20 72 6f 2c ~= search(g, ro,
0410: 20 6c 61 6d 2c 20 64 65 61 74 68 29 3b 0a 09 09 lam, death);...
0420: 7d 0a 09 09 63 61 6e 64 20 7e 3d 20 74 75 70 6c }...cand ~= tupl
0430: 65 28 27 57 27 2c 69 6e 74 2e 6d 61 78 29 3b 0a e('W',int.max);.
0440: 09 09 73 6f 72 74 21 28 28 54 75 70 6c 65 21 28 ..sort!((Tuple!(
0450: 63 68 61 72 2c 69 6e 74 29 20 63 31 2c 20 54 75 char,int) c1, Tu
0460: 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 20 63 ple!(char,int) c
0470: 32 29 7b 0a 09 09 09 69 66 28 63 31 5b 31 5d 20 2){....if(c1[1]
0480: 21 3d 20 63 32 5b 31 5d 29 0a 09 09 09 09 72 65 != c2[1]).....re
0490: 74 75 72 6e 20 63 31 5b 31 5d 20 3c 20 63 32 5b turn c1[1] < c2[
04a0: 31 5d 3b 0a 09 09 09 72 65 74 75 72 6e 20 63 31 1];....return c1
04b0: 5b 30 5d 20 3c 20 63 32 5b 30 5d 3b 0a 09 09 7d [0] < c2[0];...}
04c0: 29 28 63 61 6e 64 29 3b 0a 09 09 63 20 3d 20 63 )(cand);...c = c
04d0: 61 6e 64 5b 30 5d 5b 30 5d 3b 0a 0a 09 09 69 66 and[0][0];....if
04e0: 28 63 3d 3d 27 57 27 29 20 7b 0a 09 09 09 67 5f (c=='W') {....g_
04f0: 77 63 2b 2b 3b 0a 09 09 09 69 66 28 67 5f 77 63 wc++;....if(g_wc
0500: 20 3e 20 31 30 29 0a 09 09 09 09 63 20 3d 20 27 > 10).....c = '
0510: 41 27 3b 0a 09 09 7d 0a 09 09 65 6c 73 65 0a 09 A';...}...else..
0520: 09 09 67 5f 77 63 20 3d 20 30 3b 0a 09 09 62 6f ..g_wc = 0;...bo
0530: 6f 6c 5b 63 68 61 72 5d 20 63 68 6f 69 63 65 3b ol[char] choice;
0540: 0a 09 09 66 6f 72 65 61 63 68 28 74 3b 20 63 61 ...foreach(t; ca
0550: 6e 64 29 0a 09 09 09 63 68 6f 69 63 65 5b 74 5b nd)....choice[t[
0560: 30 5d 5d 20 3d 20 74 72 75 65 3b 0a 09 09 6c 6f 0]] = true;...lo
0570: 67 20 7e 3d 20 74 75 70 6c 65 28 72 6f 2e 63 6c g ~= tuple(ro.cl
0580: 6f 6e 65 28 29 2c 20 63 61 73 74 28 69 6e 74 29 one(), cast(int)
0590: 63 68 6f 69 63 65 2e 6c 65 6e 67 74 68 29 3b 0a choice.length);.
05a0: 09 09 69 66 28 6c 6f 67 2e 6c 65 6e 67 74 68 20 ..if(log.length
05b0: 3e 20 35 29 0a 09 09 09 6c 6f 67 20 3d 20 6c 6f > 5)....log = lo
05c0: 67 5b 24 2d 35 2e 2e 24 5d 3b 0a 09 09 69 6e 74 g[$-5..$];...int
05d0: 20 63 6e 74 20 3d 20 30 3b 0a 09 09 66 6f 72 65 cnt = 0;...fore
05e0: 61 63 68 28 6c 3b 20 6c 6f 67 29 0a 09 09 09 69 ach(l; log)....i
05f0: 66 28 6c 5b 30 5d 20 3d 3d 20 6c 6f 67 5b 24 2d f(l[0] == log[$-
0600: 31 5d 5b 30 5d 29 0a 09 09 09 09 2b 2b 63 6e 74 1][0]).....++cnt
0610: 3b 0a 09 09 69 66 28 20 63 6e 74 20 3e 3d 20 33 ;...if( cnt >= 3
0620: 20 26 26 20 62 72 65 61 74 68 3d 3d 31 20 29 20 && breath==1 )
0630: 7b 0a 09 09 09 66 6f 72 62 69 64 64 65 6e 5f 63 {....forbidden_c
0640: 65 6c 6c 5b 72 6f 2e 79 5d 5b 72 6f 2e 78 5d 20 ell[ro.y][ro.x]
0650: 3d 20 74 72 75 65 3b 0a 09 09 7d 0a 0a 09 09 72 = true;...}....r
0660: 65 74 75 72 6e 20 63 3b 0a 09 7d 0a 0a 09 54 75 eturn c;..}...Tu
0670: 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d ple!(char,int)[]
0680: 20 73 65 61 72 63 68 28 69 6e 20 47 61 6d 65 20 search(in Game
0690: 67 2c 20 69 6e 20 50 6f 73 20 73 2c 20 69 6e 20 g, in Pos s, in
06a0: 50 6f 73 20 6f 2c 20 73 74 72 69 6e 67 20 64 65 Pos o, string de
06b0: 61 74 68 29 0a 09 7b 0a 09 09 62 6f 6f 6c 20 64 ath)..{...bool d
06c0: 61 6e 67 65 72 28 69 6e 74 20 79 2c 20 69 6e 74 anger(int y, int
06d0: 20 78 29 0a 09 09 7b 0a 09 09 09 69 66 28 67 2e x)...{....if(g.
06e0: 6d 61 70 5b 79 2b 31 2c 78 5d 20 3d 3d 20 27 2a map[y+1,x] == '*
06f0: 27 29 0a 09 09 09 09 72 65 74 75 72 6e 20 74 72 ').....return tr
0700: 75 65 3b 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b ue;....if(g.map[
0710: 79 2b 31 2c 78 2d 31 5d 3d 3d 27 2a 27 20 26 26 y+1,x-1]=='*' &&
0720: 20 28 67 2e 6d 61 70 5b 79 2c 78 2d 31 5d 3d 3d (g.map[y,x-1]==
0730: 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 2d '\\'||g.map[y,x-
0740: 31 5d 3d 3d 27 2a 27 29 20 26 26 20 28 67 2e 6d 1]=='*') && (g.m
0750: 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 20 27 7c 7c ap[y+1,x]==' '||
0760: 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 52 g.map[y+1,x]=='R
0770: 27 29 29 0a 09 09 09 09 72 65 74 75 72 6e 20 74 ')).....return t
0780: 72 75 65 3b 0a 09 09 09 69 66 28 67 2e 6d 61 70 rue;....if(g.map
0790: 5b 79 2b 31 2c 78 2b 31 5d 3d 3d 27 2a 27 20 26 [y+1,x+1]=='*' &
07a0: 26 20 28 67 2e 6d 61 70 5b 79 2c 78 2b 31 5d 3d & (g.map[y,x+1]=
07b0: 3d 27 2a 27 29 20 26 26 20 28 67 2e 6d 61 70 5b ='*') && (g.map[
07c0: 79 2b 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d y+1,x]==' '||g.m
07d0: 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 52 27 29 29 ap[y+1,x]=='R'))
07e0: 0a 09 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 .....return true
07f0: 3b 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2c ;....if(g.map[y,
0800: 78 2d 31 5d 3d 3d 27 2a 27 20 26 26 20 28 67 2e x-1]=='*' && (g.
0810: 6d 61 70 5b 79 2d 31 2c 78 2d 31 5d 3d 3d 27 5c map[y-1,x-1]=='\
0820: 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2d 31 2c 78 2d \'||g.map[y-1,x-
0830: 31 5d 3d 3d 27 2a 27 29 20 26 26 20 28 67 2e 6d 1]=='*') && (g.m
0840: 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 20 27 7c 7c ap[y-1,x]==' '||
0850: 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 52 g.map[y-1,x]=='R
0860: 27 29 29 0a 09 09 09 09 72 65 74 75 72 6e 20 74 ')).....return t
0870: 72 75 65 3b 0a 09 09 09 69 66 28 67 2e 6d 61 70 rue;....if(g.map
0880: 5b 79 2c 78 2b 31 5d 3d 3d 27 2a 27 20 26 26 20 [y,x+1]=='*' &&
0890: 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 2b 31 5d 3d (g.map[y-1,x+1]=
08a0: 3d 27 2a 27 29 20 26 26 20 28 67 2e 6d 61 70 5b ='*') && (g.map[
08b0: 79 2d 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d y-1,x]==' '||g.m
08c0: 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 52 27 29 29 ap[y-1,x]=='R'))
08d0: 0a 09 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 .....return true
08e0: 3b 0a 09 09 09 72 65 74 75 72 6e 20 66 61 6c 73 ;....return fals
08f0: 65 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 61 76 6f e;...}....// avo
0900: 69 64 20 64 69 72 65 63 74 6c 79 20 62 65 6c 6f id directly belo
0910: 77 20 27 2a 27 0a 09 09 54 75 70 6c 65 21 28 63 w '*'...Tuple!(c
0920: 68 61 72 2c 69 6e 74 29 5b 5d 20 74 72 79 41 28 har,int)[] tryA(
0930: 29 20 7b 0a 09 09 09 63 6f 6e 73 74 28 50 6f 73 ) {....const(Pos
0940: 29 5b 5d 20 71 20 3d 20 5b 6f 5d 3b 0a 09 09 09 )[] q = [o];....
0950: 62 6f 6f 6c 5b 5d 5b 5d 20 76 20 3d 20 6e 65 77 bool[][] v = new
0960: 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 70 2e bool[][](g.map.
0970: 48 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 29 3b H+2, g.map.W+2);
0980: 0a 09 09 09 69 66 28 20 21 64 61 6e 67 65 72 28 ....if( !danger(
0990: 6f 2e 79 2c 6f 2e 78 29 20 29 20 7b 0a 09 09 09 o.y,o.x) ) {....
09a0: 09 76 5b 6f 2e 79 5d 5b 6f 2e 78 5d 3d 74 72 75 .v[o.y][o.x]=tru
09b0: 65 3b 0a 09 09 09 09 66 6f 72 28 69 6e 74 20 73 e;.....for(int s
09c0: 74 65 70 3d 31 3b 20 71 2e 6c 65 6e 67 74 68 3b tep=1; q.length;
09d0: 20 2b 2b 73 74 65 70 29 20 7b 0a 09 09 09 09 09 ++step) {......
09e0: 50 6f 73 5b 5d 20 71 32 3b 0a 09 09 09 09 09 66 Pos[] q2;......f
09f0: 6f 72 65 61 63 68 28 70 3b 20 71 29 20 7b 0a 09 oreach(p; q) {..
0a00: 09 09 09 09 09 69 6e 74 5b 5d 20 64 79 3d 5b 2d .....int[] dy=[-
0a10: 31 2c 2b 31 2c 30 2c 30 5d 3b 0a 09 09 09 09 09 1,+1,0,0];......
0a20: 09 69 6e 74 5b 5d 20 64 78 3d 5b 30 2c 30 2c 2d .int[] dx=[0,0,-
0a30: 31 2c 2b 31 5d 3b 0a 09 09 09 09 09 09 66 6f 72 1,+1];.......for
0a40: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 34 3b 20 2b (int i=0; i<4; +
0a50: 2b 69 29 20 7b 0a 09 09 09 09 09 09 09 69 6e 74 +i) {........int
0a60: 20 79 20 3d 20 70 2e 79 2b 64 79 5b 69 5d 3b 0a y = p.y+dy[i];.
0a70: 09 09 09 09 09 09 09 69 6e 74 20 78 20 3d 20 70 .......int x = p
0a80: 2e 78 2b 64 78 5b 69 5d 3b 0a 09 09 09 09 09 09 .x+dx[i];.......
0a90: 09 69 66 28 76 5b 79 5d 5b 78 5d 29 20 63 6f 6e .if(v[y][x]) con
0aa0: 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 09 69 66 tinue;........if
0ab0: 28 79 3d 3d 73 2e 79 20 26 26 20 78 3d 3d 73 2e (y==s.y && x==s.
0ac0: 78 29 20 7b 0a 09 09 09 09 09 09 09 09 63 68 61 x) {.........cha
0ad0: 72 20 63 20 3d 20 22 55 44 52 4c 22 5b 69 5d 3b r c = "UDRL"[i];
0ae0: 0a 09 09 09 09 09 09 09 09 69 66 28 20 64 65 61 .........if( dea
0af0: 74 68 2e 63 6f 75 6e 74 28 63 29 20 3d 3d 20 30 th.count(c) == 0
0b00: 20 29 0a 09 09 09 09 09 09 09 09 09 72 65 74 75 )..........retu
0b10: 72 6e 20 5b 74 75 70 6c 65 28 63 2c 73 74 65 70 rn [tuple(c,step
0b20: 29 5d 3b 0a 09 09 09 09 09 09 09 7d 20 65 6c 73 )];........} els
0b30: 65 20 69 66 28 66 6f 72 62 69 64 64 65 6e 5f 63 e if(forbidden_c
0b40: 65 6c 6c 5b 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 ell[y][x]){.....
0b50: 09 09 09 7d 20 65 6c 73 65 20 69 66 28 67 2e 6d ...} else if(g.m
0b60: 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e ap[y,x]==' '||g.
0b70: 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c map[y,x]=='\\'||
0b80: 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 29 g.map[y,x]=='.')
0b90: 20 7b 0a 09 09 09 09 09 09 09 09 69 66 28 64 61 {.........if(da
0ba0: 6e 67 65 72 28 79 2c 78 29 29 0a 09 09 09 09 09 nger(y,x))......
0bb0: 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 ....continue;...
0bc0: 09 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 ......q2 ~= new
0bd0: 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 Pos(y,x);.......
0be0: 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a ..v[y][x]=true;.
0bf0: 09 09 09 09 09 09 09 7d 0a 09 09 09 09 09 09 7d .......}.......}
0c00: 0a 09 09 09 09 09 7d 0a 09 09 09 09 09 71 20 3d ......}......q =
0c10: 20 71 32 3b 0a 09 09 09 09 7d 0a 09 09 09 7d 0a q2;.....}....}.
0c20: 09 09 09 72 65 74 75 72 6e 20 5b 5d 3b 0a 09 09 ...return [];...
0c30: 7d 0a 0a 09 09 2f 2f 20 61 6e 79 20 65 6d 70 74 }....// any empt
0c40: 79 20 73 70 61 63 65 20 69 73 20 6d 79 20 67 72 y space is my gr
0c50: 6f 75 6e 64 0a 09 09 54 75 70 6c 65 21 28 63 68 ound...Tuple!(ch
0c60: 61 72 2c 69 6e 74 29 5b 5d 20 74 72 79 42 28 29 ar,int)[] tryB()
0c70: 20 7b 0a 09 09 09 63 6f 6e 73 74 28 50 6f 73 29 {....const(Pos)
0c80: 5b 5d 20 71 20 3d 20 5b 6f 5d 3b 0a 09 09 09 62 [] q = [o];....b
0c90: 6f 6f 6c 5b 5d 5b 5d 20 76 20 3d 20 6e 65 77 20 ool[][] v = new
0ca0: 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 bool[][](g.map.H
0cb0: 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a +2, g.map.W+2);.
0cc0: 09 09 09 76 5b 6f 2e 79 5d 5b 6f 2e 78 5d 3d 74 ...v[o.y][o.x]=t
0cd0: 72 75 65 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 rue;....for(int
0ce0: 73 74 65 70 3d 31 30 3b 20 71 2e 6c 65 6e 67 74 step=10; q.lengt
0cf0: 68 3b 20 2b 2b 73 74 65 70 29 20 7b 0a 09 09 09 h; ++step) {....
0d00: 09 50 6f 73 5b 5d 20 71 32 3b 0a 09 09 09 09 66 .Pos[] q2;.....f
0d10: 6f 72 65 61 63 68 28 70 3b 20 71 29 20 7b 0a 09 oreach(p; q) {..
0d20: 09 09 09 09 69 6e 74 5b 5d 20 64 79 3d 5b 2d 31 ....int[] dy=[-1
0d30: 2c 2b 31 2c 30 2c 30 5d 3b 0a 09 09 09 09 09 69 ,+1,0,0];......i
0d40: 6e 74 5b 5d 20 64 78 3d 5b 30 2c 30 2c 2d 31 2c nt[] dx=[0,0,-1,
0d50: 2b 31 5d 3b 0a 09 09 09 09 09 66 6f 72 28 69 6e +1];......for(in
0d60: 74 20 69 3d 30 3b 20 69 3c 34 3b 20 2b 2b 69 29 t i=0; i<4; ++i)
0d70: 20 7b 0a 09 09 09 09 09 09 69 6e 74 20 79 20 3d {.......int y =
0d80: 20 70 2e 79 2b 64 79 5b 69 5d 3b 0a 09 09 09 09 p.y+dy[i];.....
0d90: 09 09 69 6e 74 20 78 20 3d 20 70 2e 78 2b 64 78 ..int x = p.x+dx
0da0: 5b 69 5d 3b 0a 09 09 09 09 09 09 69 66 28 76 5b [i];.......if(v[
0db0: 79 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b y][x]) continue;
0dc0: 0a 09 09 09 09 09 09 69 66 28 79 3d 3d 73 2e 79 .......if(y==s.y
0dd0: 20 26 26 20 78 3d 3d 73 2e 78 29 20 7b 0a 09 09 && x==s.x) {...
0de0: 09 09 09 09 09 63 68 61 72 20 63 20 3d 20 22 55 .....char c = "U
0df0: 44 52 4c 22 5b 69 5d 3b 0a 09 09 09 09 09 09 09 DRL"[i];........
0e00: 69 66 28 20 64 65 61 74 68 2e 63 6f 75 6e 74 28 if( death.count(
0e10: 63 29 20 3d 3d 20 30 20 29 0a 09 09 09 09 09 09 c) == 0 ).......
0e20: 09 09 72 65 74 75 72 6e 20 5b 74 75 70 6c 65 28 ..return [tuple(
0e30: 63 2c 73 74 65 70 29 5d 3b 0a 09 09 09 09 09 09 c,step)];.......
0e40: 7d 20 65 6c 73 65 20 69 66 28 66 6f 72 62 69 64 } else if(forbid
0e50: 64 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 5d 29 7b den_cell[y][x]){
0e60: 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 .......} else if
0e70: 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 (g.map[y,x]==' '
0e80: 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c ||g.map[y,x]=='\
0e90: 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d \'||g.map[y,x]==
0ea0: 27 2e 27 29 20 7b 0a 09 09 09 09 09 09 09 71 32 '.') {........q2
0eb0: 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 ~= new Pos(y,x)
0ec0: 3b 0a 09 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d ;........v[y][x]
0ed0: 3d 74 72 75 65 3b 0a 09 09 09 09 09 09 7d 0a 09 =true;.......}..
0ee0: 09 09 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 09 ....}.....}.....
0ef0: 71 20 3d 20 71 32 3b 0a 09 09 09 7d 0a 09 09 09 q = q2;....}....
0f00: 72 65 74 75 72 6e 20 5b 5d 3b 0a 09 09 7d 0a 0a return [];...}..
0f10: 09 09 2f 2f 20 70 75 73 68 20 72 6f 63 6b 73 21 ..// push rocks!
0f20: 0a 09 09 54 75 70 6c 65 21 28 63 68 61 72 2c 69 ...Tuple!(char,i
0f30: 6e 74 29 5b 5d 20 74 72 79 43 28 29 20 7b 0a 09 nt)[] tryC() {..
0f40: 09 09 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 71 ..const(Pos)[] q
0f50: 20 3d 20 5b 6f 5d 3b 0a 09 09 09 62 6f 6f 6c 5b = [o];....bool[
0f60: 5d 5b 5d 20 76 20 3d 20 6e 65 77 20 62 6f 6f 6c ][] v = new bool
0f70: 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 [][](g.map.H+2,
0f80: 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 09 76 g.map.W+2);....v
0f90: 5b 6f 2e 79 5d 5b 6f 2e 78 5d 3d 74 72 75 65 3b [o.y][o.x]=true;
0fa0: 0a 09 09 09 66 6f 72 28 69 6e 74 20 73 74 65 70 ....for(int step
0fb0: 3d 32 30 3b 20 71 2e 6c 65 6e 67 74 68 3b 20 2b =20; q.length; +
0fc0: 2b 73 74 65 70 29 20 7b 0a 09 09 09 09 50 6f 73 +step) {.....Pos
0fd0: 5b 5d 20 71 32 3b 0a 09 09 09 09 66 6f 72 65 61 [] q2;.....forea
0fe0: 63 68 28 70 3b 20 71 29 20 7b 0a 09 09 09 09 09 ch(p; q) {......
0ff0: 69 6e 74 5b 5d 20 64 79 3d 5b 2d 31 2c 2b 31 2c int[] dy=[-1,+1,
1000: 30 2c 30 5d 3b 0a 09 09 09 09 09 69 6e 74 5b 5d 0,0];......int[]
1010: 20 64 78 3d 5b 30 2c 30 2c 2d 31 2c 2b 31 5d 3b dx=[0,0,-1,+1];
1020: 0a 09 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d ......for(int i=
1030: 30 3b 20 69 3c 34 3b 20 2b 2b 69 29 20 7b 0a 09 0; i<4; ++i) {..
1040: 09 09 09 09 09 69 6e 74 20 79 20 3d 20 70 2e 79 .....int y = p.y
1050: 2b 64 79 5b 69 5d 3b 0a 09 09 09 09 09 09 69 6e +dy[i];.......in
1060: 74 20 78 20 3d 20 70 2e 78 2b 64 78 5b 69 5d 3b t x = p.x+dx[i];
1070: 0a 09 09 09 09 09 09 69 66 28 76 5b 79 5d 5b 78 .......if(v[y][x
1080: 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 ]) continue;....
1090: 09 09 09 69 66 28 79 3d 3d 73 2e 79 20 26 26 20 ...if(y==s.y &&
10a0: 78 3d 3d 73 2e 78 29 20 7b 0a 09 09 09 09 09 09 x==s.x) {.......
10b0: 09 63 68 61 72 20 63 20 3d 20 22 55 44 52 4c 22 .char c = "UDRL"
10c0: 5b 69 5d 3b 0a 09 09 09 09 09 09 09 69 66 28 20 [i];........if(
10d0: 64 65 61 74 68 2e 63 6f 75 6e 74 28 63 29 20 3d death.count(c) =
10e0: 3d 20 30 20 29 0a 09 09 09 09 09 09 09 09 72 65 = 0 ).........re
10f0: 74 75 72 6e 20 5b 74 75 70 6c 65 28 63 2c 73 74 turn [tuple(c,st
1100: 65 70 29 5d 3b 0a 09 09 09 09 09 09 7d 20 65 6c ep)];.......} el
1110: 73 65 20 69 66 28 66 6f 72 62 69 64 64 65 6e 5f se if(forbidden_
1120: 63 65 6c 6c 5b 79 5d 5b 78 5d 29 7b 0a 09 09 09 cell[y][x]){....
1130: 09 09 09 7d 20 65 6c 73 65 20 69 66 28 67 2e 6d ...} else if(g.m
1140: 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e ap[y,x]==' '||g.
1150: 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c map[y,x]=='\\'||
1160: 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 29 g.map[y,x]=='.')
1170: 20 7b 0a 09 09 09 09 09 09 09 71 32 20 7e 3d 20 {........q2 ~=
1180: 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 new Pos(y,x);...
1190: 09 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 .....v[y][x]=tru
11a0: 65 3b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 e;.......} else
11b0: 69 66 28 64 79 5b 69 5d 3d 3d 30 20 26 26 20 67 if(dy[i]==0 && g
11c0: 2e 6d 61 70 5b 70 5d 3d 3d 27 20 27 20 26 26 20 .map[p]==' ' &&
11d0: 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2a 27 20 g.map[y,x]=='*'
11e0: 26 26 20 28 67 2e 6d 61 70 5b 79 2b 64 79 5b 69 && (g.map[y+dy[i
11f0: 5d 2c 78 2b 64 78 5b 69 5d 5d 3d 3d 27 20 27 7c ],x+dx[i]]==' '|
1200: 7c 67 2e 6d 61 70 5b 79 2b 64 79 5b 69 5d 2c 78 |g.map[y+dy[i],x
1210: 2b 64 78 5b 69 5d 5d 3d 3d 27 52 27 29 29 20 7b +dx[i]]=='R')) {
1220: 0a 09 09 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 ........q2 ~= ne
1230: 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 w Pos(y,x);.....
1240: 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b ...v[y][x]=true;
1250: 0a 09 09 09 09 09 09 7d 0a 09 09 09 09 09 7d 0a .......}......}.
1260: 09 09 09 09 7d 0a 09 09 09 09 71 20 3d 20 71 32 ....}.....q = q2
1270: 3b 0a 09 09 09 7d 0a 09 09 09 72 65 74 75 72 6e ;....}....return
1280: 20 5b 5d 3b 0a 09 09 7d 0a 09 09 72 65 74 75 72 [];...}...retur
1290: 6e 20 74 72 79 41 28 29 20 7e 20 74 72 79 42 28 n tryA() ~ tryB(
12a0: 29 20 7e 20 74 72 79 43 28 29 3b 0a 09 7d 0a 7d ) ~ tryC();..}.}
12b0: 0a .