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 09 66 6f 72 62 69 clone();...forbi
0120: 64 64 65 6e 5f 63 65 6c 6c 20 3d 20 6e 65 77 20 dden_cell = new
0130: 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 bool[][](g.map.H
0140: 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a +2, g.map.W+2);.
0150: 09 7d 0a 0a 09 63 68 61 72 20 73 69 6e 67 6c 65 .}...char single
0160: 5f 73 74 65 70 28 29 0a 09 7b 0a 09 09 54 75 70 _step()..{...Tup
0170: 6c 65 21 28 73 74 72 69 6e 67 2c 69 6e 74 29 20 le!(string,int)
0180: 64 65 20 3d 20 64 65 61 74 68 5f 6d 6f 76 65 28 de = death_move(
0190: 67 29 3b 0a 09 09 63 68 61 72 20 63 20 3d 20 61 g);...char c = a
01a0: 63 74 28 67 2c 20 64 65 5b 30 5d 2c 20 64 65 5b ct(g, de[0], de[
01b0: 31 5d 29 3b 0a 09 09 67 2e 63 6f 6d 6d 61 6e 64 1]);...g.command
01c0: 28 63 29 3b 0a 09 09 72 65 74 75 72 6e 20 63 3b (c);...return c;
01d0: 0a 09 7d 0a 0a 09 54 75 70 6c 65 21 28 73 74 72 ..}...Tuple!(str
01e0: 69 6e 67 2c 69 6e 74 29 20 64 65 61 74 68 5f 6d ing,int) death_m
01f0: 6f 76 65 28 63 6f 6e 73 74 28 47 61 6d 65 29 20 ove(const(Game)
0200: 67 29 0a 09 7b 0a 09 09 73 74 72 69 6e 67 20 64 g)..{...string d
0210: 65 61 74 68 3b 0a 09 09 69 6e 74 20 63 68 6f 69 eath;...int choi
0220: 63 65 20 3d 20 30 3b 0a 09 09 66 6f 72 65 61 63 ce = 0;...foreac
0230: 68 28 63 68 61 72 20 63 3b 20 22 55 44 4c 52 57 h(char c; "UDLRW
0240: 22 29 20 7b 0a 09 09 09 47 61 6d 65 20 67 67 20 ") {....Game gg
0250: 3d 20 67 2e 63 6c 6f 6e 65 28 29 3b 0a 09 09 09 = g.clone();....
0260: 67 67 2e 63 6f 6d 6d 61 6e 64 28 63 29 3b 0a 09 gg.command(c);..
0270: 09 09 69 66 28 20 21 67 67 2e 63 6c 65 61 72 65 ..if( !gg.cleare
0280: 64 20 26 26 20 67 67 2e 64 65 61 64 20 29 0a 09 d && gg.dead )..
0290: 09 09 09 64 65 61 74 68 20 7e 3d 20 63 3b 0a 09 ...death ~= c;..
02a0: 09 09 65 6c 73 65 20 69 66 28 20 67 67 2e 6d 61 ..else if( gg.ma
02b0: 70 2e 72 6f 62 6f 74 20 21 3d 20 67 2e 6d 61 70 p.robot != g.map
02c0: 2e 72 6f 62 6f 74 20 29 0a 09 09 09 09 63 68 6f .robot ).....cho
02d0: 69 63 65 2b 2b 3b 0a 09 09 7d 0a 09 09 72 65 74 ice++;...}...ret
02e0: 75 72 6e 20 74 75 70 6c 65 28 64 65 61 74 68 2c urn tuple(death,
02f0: 20 63 68 6f 69 63 65 29 3b 0a 09 7d 0a 0a 09 54 choice);..}...T
0300: 75 70 6c 65 21 28 50 6f 73 2c 20 69 6e 74 29 5b uple!(Pos, int)[
0310: 5d 20 6c 6f 67 3b 0a 09 62 6f 6f 6c 5b 5d 5b 5d ] log;..bool[][]
0320: 20 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 3b forbidden_cell;
0330: 0a 0a 09 63 68 61 72 20 61 63 74 28 63 6f 6e 73 ...char act(cons
0340: 74 28 47 61 6d 65 29 20 67 2c 20 73 74 72 69 6e t(Game) g, strin
0350: 67 20 64 65 61 74 68 2c 20 69 6e 74 20 62 72 65 g death, int bre
0360: 61 74 68 29 0a 09 7b 0a 09 09 63 6f 6e 73 74 20 ath)..{...const
0370: 50 6f 73 20 20 20 72 6f 20 3d 20 67 2e 6d 61 70 Pos ro = g.map
0380: 2e 72 6f 62 6f 74 3b 0a 09 09 63 6f 6e 73 74 20 .robot;...const
0390: 50 6f 73 5b 5d 20 6c 61 20 3d 20 67 2e 6d 61 70 Pos[] la = g.map
03a0: 2e 6c 61 6d 62 64 61 73 28 29 3b 0a 09 09 63 6f .lambdas();...co
03b0: 6e 73 74 20 50 6f 73 20 20 20 6c 69 20 3d 20 67 nst Pos li = g
03c0: 2e 6d 61 70 2e 6c 69 66 74 3b 0a 0a 09 09 54 75 .map.lift;....Tu
03d0: 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d ple!(char,int)[]
03e0: 20 63 61 6e 64 3b 0a 09 09 63 68 61 72 20 63 20 cand;...char c
03f0: 3d 20 27 57 27 3b 0a 09 09 69 66 28 20 6c 61 2e = 'W';...if( la.
0400: 65 6d 70 74 79 20 29 20 7b 0a 09 09 09 63 61 6e empty ) {....can
0410: 64 20 3d 20 73 65 61 72 63 68 28 67 2c 20 72 6f d = search(g, ro
0420: 2c 20 6c 69 2c 20 64 65 61 74 68 29 3b 0a 09 09 , li, death);...
0430: 7d 20 65 6c 73 65 20 7b 0a 09 09 09 66 6f 72 65 } else {....fore
0440: 61 63 68 28 6c 61 6d 3b 20 6c 61 29 0a 09 09 09 ach(lam; la)....
0450: 09 63 61 6e 64 20 7e 3d 20 73 65 61 72 63 68 28 .cand ~= search(
0460: 67 2c 20 72 6f 2c 20 6c 61 6d 2c 20 64 65 61 74 g, ro, lam, deat
0470: 68 29 3b 0a 09 09 7d 0a 09 09 63 61 6e 64 20 7e h);...}...cand ~
0480: 3d 20 74 75 70 6c 65 28 27 57 27 2c 69 6e 74 2e = tuple('W',int.
0490: 6d 61 78 29 3b 0a 09 09 73 6f 72 74 21 28 28 54 max);...sort!((T
04a0: 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 20 uple!(char,int)
04b0: 63 31 2c 20 54 75 70 6c 65 21 28 63 68 61 72 2c c1, Tuple!(char,
04c0: 69 6e 74 29 20 63 32 29 7b 0a 09 09 09 69 66 28 int) c2){....if(
04d0: 63 31 5b 31 5d 20 21 3d 20 63 32 5b 31 5d 29 0a c1[1] != c2[1]).
04e0: 09 09 09 09 72 65 74 75 72 6e 20 63 31 5b 31 5d ....return c1[1]
04f0: 20 3c 20 63 32 5b 31 5d 3b 0a 09 09 09 72 65 74 < c2[1];....ret
0500: 75 72 6e 20 63 31 5b 30 5d 20 3c 20 63 32 5b 30 urn c1[0] < c2[0
0510: 5d 3b 0a 09 09 7d 29 28 63 61 6e 64 29 3b 0a 09 ];...})(cand);..
0520: 09 63 20 3d 20 63 61 6e 64 5b 30 5d 5b 30 5d 3b .c = cand[0][0];
0530: 0a 0a 09 09 69 66 28 63 3d 3d 27 57 27 29 20 7b ....if(c=='W') {
0540: 0a 09 09 09 67 5f 77 63 2b 2b 3b 0a 09 09 09 69 ....g_wc++;....i
0550: 66 28 67 5f 77 63 20 3e 20 31 30 29 0a 09 09 09 f(g_wc > 10)....
0560: 09 63 20 3d 20 27 41 27 3b 0a 09 09 7d 0a 09 09 .c = 'A';...}...
0570: 65 6c 73 65 0a 09 09 09 67 5f 77 63 20 3d 20 30 else....g_wc = 0
0580: 3b 0a 09 09 62 6f 6f 6c 5b 63 68 61 72 5d 20 63 ;...bool[char] c
0590: 68 6f 69 63 65 3b 0a 09 09 66 6f 72 65 61 63 68 hoice;...foreach
05a0: 28 74 3b 20 63 61 6e 64 29 0a 09 09 09 63 68 6f (t; cand)....cho
05b0: 69 63 65 5b 74 5b 30 5d 5d 20 3d 20 74 72 75 65 ice[t[0]] = true
05c0: 3b 0a 09 09 6c 6f 67 20 7e 3d 20 74 75 70 6c 65 ;...log ~= tuple
05d0: 28 72 6f 2e 63 6c 6f 6e 65 28 29 2c 20 63 61 73 (ro.clone(), cas
05e0: 74 28 69 6e 74 29 63 68 6f 69 63 65 2e 6c 65 6e t(int)choice.len
05f0: 67 74 68 29 3b 0a 09 09 69 66 28 6c 6f 67 2e 6c gth);...if(log.l
0600: 65 6e 67 74 68 20 3e 20 35 29 0a 09 09 09 6c 6f ength > 5)....lo
0610: 67 20 3d 20 6c 6f 67 5b 24 2d 35 2e 2e 24 5d 3b g = log[$-5..$];
0620: 0a 09 09 69 6e 74 20 63 6e 74 20 3d 20 30 3b 0a ...int cnt = 0;.
0630: 09 09 66 6f 72 65 61 63 68 28 6c 3b 20 6c 6f 67 ..foreach(l; log
0640: 29 0a 09 09 09 69 66 28 6c 5b 30 5d 20 3d 3d 20 )....if(l[0] ==
0650: 6c 6f 67 5b 24 2d 31 5d 5b 30 5d 29 0a 09 09 09 log[$-1][0])....
0660: 09 2b 2b 63 6e 74 3b 0a 09 09 69 66 28 20 63 6e .++cnt;...if( cn
0670: 74 20 3e 3d 20 33 20 26 26 20 62 72 65 61 74 68 t >= 3 && breath
0680: 3d 3d 31 20 29 20 7b 0a 09 09 09 66 6f 72 62 69 ==1 ) {....forbi
0690: 64 64 65 6e 5f 63 65 6c 6c 5b 72 6f 2e 79 5d 5b dden_cell[ro.y][
06a0: 72 6f 2e 78 5d 20 3d 20 74 72 75 65 3b 0a 09 09 ro.x] = true;...
06b0: 7d 0a 0a 09 09 72 65 74 75 72 6e 20 63 3b 0a 09 }....return c;..
06c0: 7d 0a 0a 09 54 75 70 6c 65 21 28 63 68 61 72 2c }...Tuple!(char,
06d0: 69 6e 74 29 5b 5d 20 73 65 61 72 63 68 28 69 6e int)[] search(in
06e0: 20 47 61 6d 65 20 67 2c 20 69 6e 20 50 6f 73 20 Game g, in Pos
06f0: 73 2c 20 69 6e 20 50 6f 73 20 6f 2c 20 73 74 72 s, in Pos o, str
0700: 69 6e 67 20 64 65 61 74 68 29 0a 09 7b 0a 09 09 ing death)..{...
0710: 62 6f 6f 6c 20 64 61 6e 67 65 72 28 69 6e 74 20 bool danger(int
0720: 79 2c 20 69 6e 74 20 78 29 0a 09 09 7b 0a 09 09 y, int x)...{...
0730: 09 69 66 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d .if(g.map[y+1,x]
0740: 20 3d 3d 20 27 2a 27 29 0a 09 09 09 09 72 65 74 == '*').....ret
0750: 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 28 urn true;....if(
0760: 67 2e 6d 61 70 5b 79 2b 31 2c 78 2d 31 5d 3d 3d g.map[y+1,x-1]==
0770: 27 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 2c '*' && (g.map[y,
0780: 78 2d 31 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 x-1]=='\\'||g.ma
0790: 70 5b 79 2c 78 2d 31 5d 3d 3d 27 2a 27 29 20 26 p[y,x-1]=='*') &
07a0: 26 20 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d & (g.map[y+1,x]=
07b0: 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2b 31 2c =' '||g.map[y+1,
07c0: 78 5d 3d 3d 27 52 27 29 29 0a 09 09 09 09 72 65 x]=='R')).....re
07d0: 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 turn true;....if
07e0: 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 2b 31 5d 3d (g.map[y+1,x+1]=
07f0: 3d 27 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 ='*' && (g.map[y
0800: 2c 78 2b 31 5d 3d 3d 27 2a 27 29 20 26 26 20 28 ,x+1]=='*') && (
0810: 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 20 g.map[y+1,x]=='
0820: 27 7c 7c 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d '||g.map[y+1,x]=
0830: 3d 27 52 27 29 29 0a 09 09 09 09 72 65 74 75 72 ='R')).....retur
0840: 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 28 67 2e n true;....if(g.
0850: 6d 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27 2a 27 20 map[y,x-1]=='*'
0860: 26 26 20 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 2d && (g.map[y-1,x-
0870: 31 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 1]=='\\'||g.map[
0880: 79 2d 31 2c 78 2d 31 5d 3d 3d 27 2a 27 29 20 26 y-1,x-1]=='*') &
0890: 26 20 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d & (g.map[y-1,x]=
08a0: 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2d 31 2c =' '||g.map[y-1,
08b0: 78 5d 3d 3d 27 52 27 29 29 0a 09 09 09 09 72 65 x]=='R')).....re
08c0: 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 turn true;....if
08d0: 28 67 2e 6d 61 70 5b 79 2c 78 2b 31 5d 3d 3d 27 (g.map[y,x+1]=='
08e0: 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 2d 31 *' && (g.map[y-1
08f0: 2c 78 2b 31 5d 3d 3d 27 2a 27 29 20 26 26 20 28 ,x+1]=='*') && (
0900: 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 20 g.map[y-1,x]=='
0910: 27 7c 7c 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d '||g.map[y-1,x]=
0920: 3d 27 52 27 29 29 0a 09 09 09 09 72 65 74 75 72 ='R')).....retur
0930: 6e 20 74 72 75 65 3b 0a 09 09 09 72 65 74 75 72 n true;....retur
0940: 6e 20 66 61 6c 73 65 3b 0a 09 09 7d 0a 0a 09 09 n false;...}....
0950: 2f 2f 20 61 76 6f 69 64 20 64 69 72 65 63 74 6c // avoid directl
0960: 79 20 62 65 6c 6f 77 20 27 2a 27 0a 09 09 54 75 y below '*'...Tu
0970: 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d ple!(char,int)[]
0980: 20 74 72 79 41 28 29 20 7b 0a 09 09 09 63 6f 6e tryA() {....con
0990: 73 74 28 50 6f 73 29 5b 5d 20 71 20 3d 20 5b 6f st(Pos)[] q = [o
09a0: 5d 3b 0a 09 09 09 62 6f 6f 6c 5b 5d 5b 5d 20 76 ];....bool[][] v
09b0: 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 = new bool[][](
09c0: 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 g.map.H+2, g.map
09d0: 2e 57 2b 32 29 3b 0a 09 09 09 69 66 28 20 21 64 .W+2);....if( !d
09e0: 61 6e 67 65 72 28 6f 2e 79 2c 6f 2e 78 29 20 29 anger(o.y,o.x) )
09f0: 20 7b 0a 09 09 09 09 76 5b 6f 2e 79 5d 5b 6f 2e {.....v[o.y][o.
0a00: 78 5d 3d 74 72 75 65 3b 0a 09 09 09 09 66 6f 72 x]=true;.....for
0a10: 28 69 6e 74 20 73 74 65 70 3d 31 3b 20 71 2e 6c (int step=1; q.l
0a20: 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 29 20 7b ength; ++step) {
0a30: 0a 09 09 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a ......Pos[] q2;.
0a40: 09 09 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 .....foreach(p;
0a50: 71 29 20 7b 0a 09 09 09 09 09 09 69 6e 74 5b 5d q) {.......int[]
0a60: 20 64 79 3d 5b 2d 31 2c 2b 31 2c 30 2c 30 5d 3b dy=[-1,+1,0,0];
0a70: 0a 09 09 09 09 09 09 69 6e 74 5b 5d 20 64 78 3d .......int[] dx=
0a80: 5b 30 2c 30 2c 2d 31 2c 2b 31 5d 3b 0a 09 09 09 [0,0,-1,+1];....
0a90: 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
0aa0: 69 3c 34 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 i<4; ++i) {.....
0ab0: 09 09 09 69 6e 74 20 79 20 3d 20 70 2e 79 2b 64 ...int y = p.y+d
0ac0: 79 5b 69 5d 3b 0a 09 09 09 09 09 09 09 69 6e 74 y[i];........int
0ad0: 20 78 20 3d 20 70 2e 78 2b 64 78 5b 69 5d 3b 0a x = p.x+dx[i];.
0ae0: 09 09 09 09 09 09 09 69 66 28 76 5b 79 5d 5b 78 .......if(v[y][x
0af0: 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 ]) continue;....
0b00: 09 09 09 09 69 66 28 79 3d 3d 73 2e 79 20 26 26 ....if(y==s.y &&
0b10: 20 78 3d 3d 73 2e 78 29 20 7b 0a 09 09 09 09 09 x==s.x) {......
0b20: 09 09 09 63 68 61 72 20 63 20 3d 20 22 55 44 52 ...char c = "UDR
0b30: 4c 22 5b 69 5d 3b 0a 09 09 09 09 09 09 09 09 69 L"[i];.........i
0b40: 66 28 20 64 65 61 74 68 2e 63 6f 75 6e 74 28 63 f( death.count(c
0b50: 29 20 3d 3d 20 30 20 29 0a 09 09 09 09 09 09 09 ) == 0 )........
0b60: 09 09 72 65 74 75 72 6e 20 5b 74 75 70 6c 65 28 ..return [tuple(
0b70: 63 2c 73 74 65 70 29 5d 3b 0a 09 09 09 09 09 09 c,step)];.......
0b80: 09 7d 20 65 6c 73 65 20 69 66 28 66 6f 72 62 69 .} else if(forbi
0b90: 64 64 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 5d 29 dden_cell[y][x])
0ba0: 7b 0a 09 09 09 09 09 09 09 7d 20 65 6c 73 65 20 {........} else
0bb0: 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 if(g.map[y,x]=='
0bc0: 20 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d '||g.map[y,x]==
0bd0: 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d '\\'||g.map[y,x]
0be0: 3d 3d 27 2e 27 29 20 7b 0a 09 09 09 09 09 09 09 =='.') {........
0bf0: 09 69 66 28 64 61 6e 67 65 72 28 79 2c 78 29 29 .if(danger(y,x))
0c00: 0a 09 09 09 09 09 09 09 09 09 63 6f 6e 74 69 6e ..........contin
0c10: 75 65 3b 0a 09 09 09 09 09 09 09 09 71 32 20 7e ue;.........q2 ~
0c20: 3d 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a = new Pos(y,x);.
0c30: 09 09 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d 3d ........v[y][x]=
0c40: 74 72 75 65 3b 0a 09 09 09 09 09 09 09 7d 0a 09 true;........}..
0c50: 09 09 09 09 09 7d 0a 09 09 09 09 09 7d 0a 09 09 .....}......}...
0c60: 09 09 09 71 20 3d 20 71 32 3b 0a 09 09 09 09 7d ...q = q2;.....}
0c70: 0a 09 09 09 7d 0a 09 09 09 72 65 74 75 72 6e 20 ....}....return
0c80: 5b 5d 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 61 6e [];...}....// an
0c90: 79 20 65 6d 70 74 79 20 73 70 61 63 65 20 69 73 y empty space is
0ca0: 20 6d 79 20 67 72 6f 75 6e 64 0a 09 09 54 75 70 my ground...Tup
0cb0: 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d 20 le!(char,int)[]
0cc0: 74 72 79 42 28 29 20 7b 0a 09 09 09 63 6f 6e 73 tryB() {....cons
0cd0: 74 28 50 6f 73 29 5b 5d 20 71 20 3d 20 5b 6f 5d t(Pos)[] q = [o]
0ce0: 3b 0a 09 09 09 62 6f 6f 6c 5b 5d 5b 5d 20 76 20 ;....bool[][] v
0cf0: 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 = new bool[][](g
0d00: 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 2e .map.H+2, g.map.
0d10: 57 2b 32 29 3b 0a 09 09 09 76 5b 6f 2e 79 5d 5b W+2);....v[o.y][
0d20: 6f 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 09 66 6f o.x]=true;....fo
0d30: 72 28 69 6e 74 20 73 74 65 70 3d 31 30 3b 20 71 r(int step=10; q
0d40: 2e 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 29 .length; ++step)
0d50: 20 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 71 32 3b {.....Pos[] q2;
0d60: 0a 09 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 .....foreach(p;
0d70: 71 29 20 7b 0a 09 09 09 09 09 69 6e 74 5b 5d 20 q) {......int[]
0d80: 64 79 3d 5b 2d 31 2c 2b 31 2c 30 2c 30 5d 3b 0a dy=[-1,+1,0,0];.
0d90: 09 09 09 09 09 69 6e 74 5b 5d 20 64 78 3d 5b 30 .....int[] dx=[0
0da0: 2c 30 2c 2d 31 2c 2b 31 5d 3b 0a 09 09 09 09 09 ,0,-1,+1];......
0db0: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 34 for(int i=0; i<4
0dc0: 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 09 69 ; ++i) {.......i
0dd0: 6e 74 20 79 20 3d 20 70 2e 79 2b 64 79 5b 69 5d nt y = p.y+dy[i]
0de0: 3b 0a 09 09 09 09 09 09 69 6e 74 20 78 20 3d 20 ;.......int x =
0df0: 70 2e 78 2b 64 78 5b 69 5d 3b 0a 09 09 09 09 09 p.x+dx[i];......
0e00: 09 69 66 28 76 5b 79 5d 5b 78 5d 29 20 63 6f 6e .if(v[y][x]) con
0e10: 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 69 66 28 tinue;.......if(
0e20: 79 3d 3d 73 2e 79 20 26 26 20 78 3d 3d 73 2e 78 y==s.y && x==s.x
0e30: 29 20 7b 0a 09 09 09 09 09 09 09 63 68 61 72 20 ) {........char
0e40: 63 20 3d 20 22 55 44 52 4c 22 5b 69 5d 3b 0a 09 c = "UDRL"[i];..
0e50: 09 09 09 09 09 09 69 66 28 20 64 65 61 74 68 2e ......if( death.
0e60: 63 6f 75 6e 74 28 63 29 20 3d 3d 20 30 20 29 0a count(c) == 0 ).
0e70: 09 09 09 09 09 09 09 09 72 65 74 75 72 6e 20 5b ........return [
0e80: 74 75 70 6c 65 28 63 2c 73 74 65 70 29 5d 3b 0a tuple(c,step)];.
0e90: 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 ......} else if(
0ea0: 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 5b 79 forbidden_cell[y
0eb0: 5d 5b 78 5d 29 7b 0a 09 09 09 09 09 09 7d 20 65 ][x]){.......} e
0ec0: 6c 73 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78 lse if(g.map[y,x
0ed0: 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2c ]==' '||g.map[y,
0ee0: 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b x]=='\\'||g.map[
0ef0: 79 2c 78 5d 3d 3d 27 2e 27 29 20 7b 0a 09 09 09 y,x]=='.') {....
0f00: 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 50 6f ....q2 ~= new Po
0f10: 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 09 76 s(y,x);........v
0f20: 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09 [y][x]=true;....
0f30: 09 09 09 7d 0a 09 09 09 09 09 7d 0a 09 09 09 09 ...}......}.....
0f40: 7d 0a 09 09 09 09 71 20 3d 20 71 32 3b 0a 09 09 }.....q = q2;...
0f50: 09 7d 0a 09 09 09 72 65 74 75 72 6e 20 5b 5d 3b .}....return [];
0f60: 0a 09 09 7d 0a 0a 09 09 2f 2f 20 70 75 73 68 20 ...}....// push
0f70: 72 6f 63 6b 73 21 0a 09 09 54 75 70 6c 65 21 28 rocks!...Tuple!(
0f80: 63 68 61 72 2c 69 6e 74 29 5b 5d 20 74 72 79 43 char,int)[] tryC
0f90: 28 29 20 7b 0a 09 09 09 63 6f 6e 73 74 28 50 6f () {....const(Po
0fa0: 73 29 5b 5d 20 71 20 3d 20 5b 6f 5d 3b 0a 09 09 s)[] q = [o];...
0fb0: 09 62 6f 6f 6c 5b 5d 5b 5d 20 76 20 3d 20 6e 65 .bool[][] v = ne
0fc0: 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 70 w bool[][](g.map
0fd0: 2e 48 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 29 .H+2, g.map.W+2)
0fe0: 3b 0a 09 09 09 76 5b 6f 2e 79 5d 5b 6f 2e 78 5d ;....v[o.y][o.x]
0ff0: 3d 74 72 75 65 3b 0a 09 09 09 66 6f 72 28 69 6e =true;....for(in
1000: 74 20 73 74 65 70 3d 32 30 3b 20 71 2e 6c 65 6e t step=20; q.len
1010: 67 74 68 3b 20 2b 2b 73 74 65 70 29 20 7b 0a 09 gth; ++step) {..
1020: 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a 09 09 09 ...Pos[] q2;....
1030: 09 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 7b .foreach(p; q) {
1040: 0a 09 09 09 09 09 69 6e 74 5b 5d 20 64 79 3d 5b ......int[] dy=[
1050: 2d 31 2c 2b 31 2c 30 2c 30 5d 3b 0a 09 09 09 09 -1,+1,0,0];.....
1060: 09 69 6e 74 5b 5d 20 64 78 3d 5b 30 2c 30 2c 2d .int[] dx=[0,0,-
1070: 31 2c 2b 31 5d 3b 0a 09 09 09 09 09 66 6f 72 28 1,+1];......for(
1080: 69 6e 74 20 69 3d 30 3b 20 69 3c 34 3b 20 2b 2b int i=0; i<4; ++
1090: 69 29 20 7b 0a 09 09 09 09 09 09 69 6e 74 20 79 i) {.......int y
10a0: 20 3d 20 70 2e 79 2b 64 79 5b 69 5d 3b 0a 09 09 = p.y+dy[i];...
10b0: 09 09 09 09 69 6e 74 20 78 20 3d 20 70 2e 78 2b ....int x = p.x+
10c0: 64 78 5b 69 5d 3b 0a 09 09 09 09 09 09 69 66 28 dx[i];.......if(
10d0: 76 5b 79 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e 75 v[y][x]) continu
10e0: 65 3b 0a 09 09 09 09 09 09 69 66 28 79 3d 3d 73 e;.......if(y==s
10f0: 2e 79 20 26 26 20 78 3d 3d 73 2e 78 29 20 7b 0a .y && x==s.x) {.
1100: 09 09 09 09 09 09 09 63 68 61 72 20 63 20 3d 20 .......char c =
1110: 22 55 44 52 4c 22 5b 69 5d 3b 0a 09 09 09 09 09 "UDRL"[i];......
1120: 09 09 69 66 28 20 64 65 61 74 68 2e 63 6f 75 6e ..if( death.coun
1130: 74 28 63 29 20 3d 3d 20 30 20 29 0a 09 09 09 09 t(c) == 0 ).....
1140: 09 09 09 09 72 65 74 75 72 6e 20 5b 74 75 70 6c ....return [tupl
1150: 65 28 63 2c 73 74 65 70 29 5d 3b 0a 09 09 09 09 e(c,step)];.....
1160: 09 09 7d 20 65 6c 73 65 20 69 66 28 66 6f 72 62 ..} else if(forb
1170: 69 64 64 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 5d idden_cell[y][x]
1180: 29 7b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 ){.......} else
1190: 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 if(g.map[y,x]=='
11a0: 20 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d '||g.map[y,x]==
11b0: 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d '\\'||g.map[y,x]
11c0: 3d 3d 27 2e 27 29 20 7b 0a 09 09 09 09 09 09 09 =='.') {........
11d0: 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c q2 ~= new Pos(y,
11e0: 78 29 3b 0a 09 09 09 09 09 09 09 76 5b 79 5d 5b x);........v[y][
11f0: 78 5d 3d 74 72 75 65 3b 0a 09 09 09 09 09 09 7d x]=true;.......}
1200: 20 65 6c 73 65 20 69 66 28 64 79 5b 69 5d 3d 3d else if(dy[i]==
1210: 30 20 26 26 20 67 2e 6d 61 70 5b 70 5d 3d 3d 27 0 && g.map[p]=='
1220: 20 27 20 26 26 20 67 2e 6d 61 70 5b 79 2c 78 5d ' && g.map[y,x]
1230: 3d 3d 27 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b =='*' && (g.map[
1240: 79 2b 64 79 5b 69 5d 2c 78 2b 64 78 5b 69 5d 5d y+dy[i],x+dx[i]]
1250: 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2b 64 ==' '||g.map[y+d
1260: 79 5b 69 5d 2c 78 2b 64 78 5b 69 5d 5d 3d 3d 27 y[i],x+dx[i]]=='
1270: 52 27 29 29 20 7b 0a 09 09 09 09 09 09 09 71 32 R')) {........q2
1280: 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 ~= new Pos(y,x)
1290: 3b 0a 09 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d ;........v[y][x]
12a0: 3d 74 72 75 65 3b 0a 09 09 09 09 09 09 7d 0a 09 =true;.......}..
12b0: 09 09 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 09 ....}.....}.....
12c0: 71 20 3d 20 71 32 3b 0a 09 09 09 7d 0a 09 09 09 q = q2;....}....
12d0: 72 65 74 75 72 6e 20 5b 5d 3b 0a 09 09 7d 0a 09 return [];...}..
12e0: 09 72 65 74 75 72 6e 20 74 72 79 41 28 29 20 7e .return tryA() ~
12f0: 20 74 72 79 42 28 29 20 7e 20 74 72 79 43 28 29 tryB() ~ tryC()
1300: 3b 0a 09 7d 0a 7d 0a ;..}.}.