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