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 5b 6c 69 5d 2c 20 64 65 61 74 68 29 3b 0a , [li], death);.
03e0: 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 09 63 61 ..} else {....ca
03f0: 6e 64 20 7e 3d 20 73 65 61 72 63 68 28 67 2c 20 nd ~= search(g,
0400: 72 6f 2c 20 6c 61 2c 20 64 65 61 74 68 29 3b 0a ro, la, death);.
0410: 09 09 7d 0a 09 09 69 66 28 63 61 6e 64 2e 65 6d ..}...if(cand.em
0420: 70 74 79 29 20 7b 0a 09 09 09 63 6f 6e 73 74 28 pty) {....const(
0430: 50 6f 73 29 5b 5d 20 74 67 74 3b 0a 09 09 09 66 Pos)[] tgt;....f
0440: 6f 72 28 69 6e 74 20 79 3d 31 3b 20 79 3c 3d 67 or(int y=1; y<=g
0450: 2e 6d 61 70 2e 48 3b 20 2b 2b 79 29 0a 09 09 09 .map.H; ++y)....
0460: 66 6f 72 28 69 6e 74 20 78 3d 31 3b 20 78 3c 3d for(int x=1; x<=
0470: 67 2e 6d 61 70 2e 57 3b 20 2b 2b 78 29 0a 09 09 g.map.W; ++x)...
0480: 09 09 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d ..if(g.map[y,x]=
0490: 3d 27 2e 27 29 0a 09 09 09 09 09 69 66 28 67 2e ='.')......if(g.
04a0: 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 2a 27 7c map[y+1,x]=='*'|
04b0: 7c 67 2e 6d 61 70 5b 79 2b 31 2c 78 2d 31 5d 3d |g.map[y+1,x-1]=
04c0: 3d 27 2a 27 7c 7c 67 2e 6d 61 70 5b 79 2b 31 2c ='*'||g.map[y+1,
04d0: 78 2b 31 5d 3d 3d 27 2a 27 0a 09 09 09 09 09 20 x+1]=='*'......
04e0: 7c 7c 67 2e 6d 61 70 5b 79 2c 78 2b 31 5d 3d 3d ||g.map[y,x+1]==
04f0: 27 2a 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 2d 31 '*'||g.map[y,x-1
0500: 5d 3d 3d 27 2a 27 29 0a 09 09 09 09 09 09 74 67 ]=='*').......tg
0510: 74 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c 78 t ~= new Pos(y,x
0520: 29 3b 0a 09 09 09 63 61 6e 64 20 7e 3d 20 73 65 );....cand ~= se
0530: 61 72 63 68 28 67 2c 20 72 6f 2c 20 74 67 74 2c arch(g, ro, tgt,
0540: 20 64 65 61 74 68 29 3b 0a 09 09 7d 0a 0a 09 09 death);...}....
0550: 69 66 28 63 61 6e 64 2e 65 6d 70 74 79 29 0a 09 if(cand.empty)..
0560: 09 09 63 61 6e 64 20 7e 3d 20 74 75 70 6c 65 28 ..cand ~= tuple(
0570: 27 57 27 2c 69 6e 74 2e 6d 61 78 29 3b 0a 09 09 'W',int.max);...
0580: 73 6f 72 74 21 28 28 54 75 70 6c 65 21 28 63 68 sort!((Tuple!(ch
0590: 61 72 2c 69 6e 74 29 20 63 31 2c 20 54 75 70 6c ar,int) c1, Tupl
05a0: 65 21 28 63 68 61 72 2c 69 6e 74 29 20 63 32 29 e!(char,int) c2)
05b0: 7b 0a 09 09 09 69 66 28 63 31 5b 31 5d 20 21 3d {....if(c1[1] !=
05c0: 20 63 32 5b 31 5d 29 0a 09 09 09 09 72 65 74 75 c2[1]).....retu
05d0: 72 6e 20 63 31 5b 31 5d 20 3c 20 63 32 5b 31 5d rn c1[1] < c2[1]
05e0: 3b 0a 09 09 09 72 65 74 75 72 6e 20 63 31 5b 30 ;....return c1[0
05f0: 5d 20 3c 20 63 32 5b 30 5d 3b 0a 09 09 7d 29 28 ] < c2[0];...})(
0600: 63 61 6e 64 29 3b 0a 09 09 63 20 3d 20 63 61 6e cand);...c = can
0610: 64 5b 30 5d 5b 30 5d 3b 0a 0a 09 09 69 66 28 64 d[0][0];....if(d
0620: 65 61 74 68 2e 63 6f 75 6e 74 28 63 29 29 20 7b eath.count(c)) {
0630: 0a 09 09 09 66 6f 72 65 61 63 68 28 63 68 61 72 ....foreach(char
0640: 20 6c 69 76 65 3b 20 22 55 44 4c 52 57 41 22 29 live; "UDLRWA")
0650: 0a 09 09 09 09 69 66 28 64 65 61 74 68 2e 63 6f .....if(death.co
0660: 75 6e 74 28 6c 69 76 65 29 3d 3d 30 29 20 7b 0a unt(live)==0) {.
0670: 09 09 09 09 09 63 3d 6c 69 76 65 3b 0a 09 09 09 .....c=live;....
0680: 09 09 62 72 65 61 6b 3b 0a 09 09 09 09 7d 0a 09 ..break;.....}..
0690: 09 7d 0a 0a 09 09 69 66 28 63 3d 3d 27 57 27 29 .}....if(c=='W')
06a0: 20 7b 0a 09 09 09 77 61 69 74 5f 63 6f 75 6e 74 {....wait_count
06b0: 2b 2b 3b 0a 09 09 09 69 66 28 77 61 69 74 5f 63 ++;....if(wait_c
06c0: 6f 75 6e 74 20 3e 20 67 2e 6d 61 70 2e 48 29 0a ount > g.map.H).
06d0: 09 09 09 09 63 20 3d 20 27 41 27 3b 0a 09 09 7d ....c = 'A';...}
06e0: 0a 09 09 65 6c 73 65 0a 09 09 09 77 61 69 74 5f ...else....wait_
06f0: 63 6f 75 6e 74 20 3d 20 30 3b 0a 0a 09 09 62 6f count = 0;....bo
0700: 6f 6c 5b 63 68 61 72 5d 20 63 68 6f 69 63 65 3b ol[char] choice;
0710: 0a 09 09 66 6f 72 65 61 63 68 28 74 3b 20 63 61 ...foreach(t; ca
0720: 6e 64 29 0a 09 09 09 63 68 6f 69 63 65 5b 74 5b nd)....choice[t[
0730: 30 5d 5d 20 3d 20 74 72 75 65 3b 0a 09 09 6c 6f 0]] = true;...lo
0740: 67 20 7e 3d 20 74 75 70 6c 65 28 72 6f 2e 63 6c g ~= tuple(ro.cl
0750: 6f 6e 65 28 29 2c 20 63 61 73 74 28 69 6e 74 29 one(), cast(int)
0760: 63 68 6f 69 63 65 2e 6c 65 6e 67 74 68 29 3b 0a choice.length);.
0770: 09 09 69 66 28 6c 6f 67 2e 6c 65 6e 67 74 68 20 ..if(log.length
0780: 3e 20 35 29 0a 09 09 09 6c 6f 67 20 3d 20 6c 6f > 5)....log = lo
0790: 67 5b 24 2d 35 2e 2e 24 5d 3b 0a 09 09 69 6e 74 g[$-5..$];...int
07a0: 20 63 6e 74 20 3d 20 30 3b 0a 09 09 66 6f 72 65 cnt = 0;...fore
07b0: 61 63 68 28 6c 3b 20 6c 6f 67 29 0a 09 09 09 69 ach(l; log)....i
07c0: 66 28 6c 5b 30 5d 20 3d 3d 20 6c 6f 67 5b 24 2d f(l[0] == log[$-
07d0: 31 5d 5b 30 5d 29 0a 09 09 09 09 2b 2b 63 6e 74 1][0]).....++cnt
07e0: 3b 0a 09 09 69 66 28 20 63 6e 74 20 3e 3d 20 33 ;...if( cnt >= 3
07f0: 20 26 26 20 62 72 65 61 74 68 3d 3d 31 20 29 20 && breath==1 )
0800: 7b 0a 09 09 09 66 6f 72 62 69 64 64 65 6e 5f 63 {....forbidden_c
0810: 65 6c 6c 5b 72 6f 2e 79 5d 5b 72 6f 2e 78 5d 20 ell[ro.y][ro.x]
0820: 3d 20 74 72 75 65 3b 0a 09 09 7d 0a 0a 09 09 72 = true;...}....r
0830: 65 74 75 72 6e 20 63 3b 0a 09 7d 0a 0a 09 54 75 eturn c;..}...Tu
0840: 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d ple!(char,int)[]
0850: 20 73 65 61 72 63 68 28 69 6e 20 47 61 6d 65 20 search(in Game
0860: 67 2c 20 69 6e 20 50 6f 73 20 73 2c 20 69 6e 20 g, in Pos s, in
0870: 50 6f 73 5b 5d 20 67 73 2c 20 73 74 72 69 6e 67 Pos[] gs, string
0880: 20 64 65 61 74 68 29 0a 09 7b 0a 09 09 62 6f 6f death)..{...boo
0890: 6c 20 64 61 6e 67 65 72 28 69 6e 74 20 79 2c 20 l danger(int y,
08a0: 69 6e 74 20 78 29 0a 09 09 7b 0a 09 09 09 69 66 int x)...{....if
08b0: 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 20 3d 3d (g.map[y+1,x] ==
08c0: 20 27 2a 27 29 0a 09 09 09 09 72 65 74 75 72 6e '*').....return
08d0: 20 74 72 75 65 3b 0a 09 09 09 69 66 28 67 2e 6d true;....if(g.m
08e0: 61 70 5b 79 2b 31 2c 78 2d 31 5d 3d 3d 27 2a 27 ap[y+1,x-1]=='*'
08f0: 20 26 26 20 28 67 2e 6d 61 70 5b 79 2c 78 2d 31 && (g.map[y,x-1
0900: 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 ]=='\\'||g.map[y
0910: 2c 78 2d 31 5d 3d 3d 27 2a 27 29 20 26 26 20 28 ,x-1]=='*') && (
0920: 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 20 g.map[y+1,x]=='
0930: 27 7c 7c 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d '||g.map[y+1,x]=
0940: 3d 27 52 27 29 29 0a 09 09 09 09 72 65 74 75 72 ='R')).....retur
0950: 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 28 67 2e n true;....if(g.
0960: 6d 61 70 5b 79 2b 31 2c 78 2b 31 5d 3d 3d 27 2a map[y+1,x+1]=='*
0970: 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 2c 78 2b ' && (g.map[y,x+
0980: 31 5d 3d 3d 27 2a 27 29 20 26 26 20 28 67 2e 6d 1]=='*') && (g.m
0990: 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 20 27 7c 7c ap[y+1,x]==' '||
09a0: 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 52 g.map[y+1,x]=='R
09b0: 27 29 29 0a 09 09 09 09 72 65 74 75 72 6e 20 74 ')).....return t
09c0: 72 75 65 3b 0a 09 09 09 69 66 28 67 2e 6d 61 70 rue;....if(g.map
09d0: 5b 79 2c 78 2d 31 5d 3d 3d 27 2a 27 20 26 26 20 [y,x-1]=='*' &&
09e0: 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 2d 31 5d 3d (g.map[y-1,x-1]=
09f0: 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2d 31 ='\\'||g.map[y-1
0a00: 2c 78 2d 31 5d 3d 3d 27 2a 27 29 20 26 26 20 28 ,x-1]=='*') && (
0a10: 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 20 g.map[y-1,x]=='
0a20: 27 7c 7c 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d '||g.map[y-1,x]=
0a30: 3d 27 52 27 29 29 0a 09 09 09 09 72 65 74 75 72 ='R')).....retur
0a40: 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 28 67 2e n true;....if(g.
0a50: 6d 61 70 5b 79 2c 78 2b 31 5d 3d 3d 27 2a 27 20 map[y,x+1]=='*'
0a60: 26 26 20 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 2b && (g.map[y-1,x+
0a70: 31 5d 3d 3d 27 2a 27 29 20 26 26 20 28 67 2e 6d 1]=='*') && (g.m
0a80: 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 20 27 7c 7c ap[y-1,x]==' '||
0a90: 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 52 g.map[y-1,x]=='R
0aa0: 27 29 29 0a 09 09 09 09 72 65 74 75 72 6e 20 74 ')).....return t
0ab0: 72 75 65 3b 0a 09 09 09 72 65 74 75 72 6e 20 66 rue;....return f
0ac0: 61 6c 73 65 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 alse;...}....//
0ad0: 61 76 6f 69 64 20 64 69 72 65 63 74 6c 79 20 62 avoid directly b
0ae0: 65 6c 6f 77 20 27 2a 27 0a 09 09 54 75 70 6c 65 elow '*'...Tuple
0af0: 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d 20 74 72 !(char,int)[] tr
0b00: 79 41 28 29 20 7b 0a 09 09 09 63 6f 6e 73 74 28 yA() {....const(
0b10: 50 6f 73 29 5b 5d 20 71 3b 0a 09 09 09 66 6f 72 Pos)[] q;....for
0b20: 65 61 63 68 28 70 3b 20 67 73 29 0a 09 09 09 09 each(p; gs).....
0b30: 69 66 28 21 64 61 6e 67 65 72 28 70 2e 79 2c 70 if(!danger(p.y,p
0b40: 2e 78 29 29 0a 09 09 09 09 09 71 20 7e 3d 20 70 .x))......q ~= p
0b50: 3b 0a 09 09 09 62 6f 6f 6c 5b 5d 5b 5d 20 76 20 ;....bool[][] v
0b60: 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 = new bool[][](g
0b70: 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 2e .map.H+2, g.map.
0b80: 57 2b 32 29 3b 0a 09 09 09 66 6f 72 65 61 63 68 W+2);....foreach
0b90: 28 70 3b 20 71 29 20 76 5b 70 2e 79 5d 5b 70 2e (p; q) v[p.y][p.
0ba0: 78 5d 3d 74 72 75 65 3b 0a 09 09 09 66 6f 72 28 x]=true;....for(
0bb0: 69 6e 74 20 73 74 65 70 3d 31 3b 20 71 2e 6c 65 int step=1; q.le
0bc0: 6e 67 74 68 3b 20 2b 2b 73 74 65 70 29 20 7b 0a ngth; ++step) {.
0bd0: 09 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a 09 09 ....Pos[] q2;...
0be0: 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 ..foreach(p; q)
0bf0: 7b 0a 09 09 09 09 09 69 6e 74 5b 5d 20 64 79 3d {......int[] dy=
0c00: 5b 2d 31 2c 2b 31 2c 30 2c 30 5d 3b 0a 09 09 09 [-1,+1,0,0];....
0c10: 09 09 69 6e 74 5b 5d 20 64 78 3d 5b 30 2c 30 2c ..int[] dx=[0,0,
0c20: 2d 31 2c 2b 31 5d 3b 0a 09 09 09 09 09 66 6f 72 -1,+1];......for
0c30: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 34 3b 20 2b (int i=0; i<4; +
0c40: 2b 69 29 20 7b 0a 09 09 09 09 09 09 69 6e 74 20 +i) {.......int
0c50: 79 20 3d 20 70 2e 79 2b 64 79 5b 69 5d 3b 0a 09 y = p.y+dy[i];..
0c60: 09 09 09 09 09 69 6e 74 20 78 20 3d 20 70 2e 78 .....int x = p.x
0c70: 2b 64 78 5b 69 5d 3b 0a 09 09 09 09 09 09 69 66 +dx[i];.......if
0c80: 28 76 5b 79 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e (v[y][x]) contin
0c90: 75 65 3b 0a 09 09 09 09 09 09 69 66 28 79 3d 3d ue;.......if(y==
0ca0: 73 2e 79 20 26 26 20 78 3d 3d 73 2e 78 29 20 7b s.y && x==s.x) {
0cb0: 0a 09 09 09 09 09 09 09 63 68 61 72 20 63 20 3d ........char c =
0cc0: 20 22 55 44 52 4c 22 5b 69 5d 3b 0a 09 09 09 09 "UDRL"[i];.....
0cd0: 09 09 09 69 66 28 20 64 65 61 74 68 2e 63 6f 75 ...if( death.cou
0ce0: 6e 74 28 63 29 20 3d 3d 20 30 20 29 0a 09 09 09 nt(c) == 0 )....
0cf0: 09 09 09 09 09 72 65 74 75 72 6e 20 5b 74 75 70 .....return [tup
0d00: 6c 65 28 63 2c 73 74 65 70 29 5d 3b 0a 09 09 09 le(c,step)];....
0d10: 09 09 09 7d 20 65 6c 73 65 20 69 66 28 66 6f 72 ...} else if(for
0d20: 62 69 64 64 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 bidden_cell[y][x
0d30: 5d 29 7b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 ]){.......} else
0d40: 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d if(g.map[y,x]==
0d50: 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d ' '||g.map[y,x]=
0d60: 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 ='\\'||g.map[y,x
0d70: 5d 3d 3d 27 2e 27 29 20 7b 0a 09 09 09 09 09 09 ]=='.') {.......
0d80: 09 69 66 28 64 61 6e 67 65 72 28 79 2c 78 29 29 .if(danger(y,x))
0d90: 0a 09 09 09 09 09 09 09 09 63 6f 6e 74 69 6e 75 .........continu
0da0: 65 3b 0a 09 09 09 09 09 09 09 71 32 20 7e 3d 20 e;........q2 ~=
0db0: 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 new Pos(y,x);...
0dc0: 09 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 .....v[y][x]=tru
0dd0: 65 3b 0a 09 09 09 09 09 09 7d 0a 09 09 09 09 09 e;.......}......
0de0: 7d 0a 09 09 09 09 7d 0a 09 09 09 09 71 20 3d 20 }.....}.....q =
0df0: 71 32 3b 0a 09 09 09 7d 0a 09 09 09 72 65 74 75 q2;....}....retu
0e00: 72 6e 20 5b 5d 3b 0a 09 09 7d 0a 0a 09 09 2f 2f rn [];...}....//
0e10: 20 61 6e 79 20 65 6d 70 74 79 20 73 70 61 63 65 any empty space
0e20: 20 69 73 20 6d 79 20 67 72 6f 75 6e 64 0a 09 09 is my ground...
0e30: 54 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 Tuple!(char,int)
0e40: 5b 5d 20 74 72 79 42 28 29 20 7b 0a 09 09 09 63 [] tryB() {....c
0e50: 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 71 3b 0a 09 onst(Pos)[] q;..
0e60: 09 09 66 6f 72 65 61 63 68 28 70 3b 20 67 73 29 ..foreach(p; gs)
0e70: 20 71 20 7e 3d 20 70 3b 0a 09 09 09 62 6f 6f 6c q ~= p;....bool
0e80: 5b 5d 5b 5d 20 76 20 3d 20 6e 65 77 20 62 6f 6f [][] v = new boo
0e90: 6c 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c l[][](g.map.H+2,
0ea0: 20 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 09 g.map.W+2);....
0eb0: 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 76 5b foreach(p; q) v[
0ec0: 70 2e 79 5d 5b 70 2e 78 5d 3d 74 72 75 65 3b 0a p.y][p.x]=true;.
0ed0: 09 09 09 66 6f 72 28 69 6e 74 20 73 74 65 70 3d ...for(int step=
0ee0: 31 30 3b 20 71 2e 6c 65 6e 67 74 68 3b 20 2b 2b 10; q.length; ++
0ef0: 73 74 65 70 29 20 7b 0a 09 09 09 09 50 6f 73 5b step) {.....Pos[
0f00: 5d 20 71 32 3b 0a 09 09 09 09 66 6f 72 65 61 63 ] q2;.....foreac
0f10: 68 28 70 3b 20 71 29 20 7b 0a 09 09 09 09 09 69 h(p; q) {......i
0f20: 6e 74 5b 5d 20 64 79 3d 5b 2d 31 2c 2b 31 2c 30 nt[] dy=[-1,+1,0
0f30: 2c 30 5d 3b 0a 09 09 09 09 09 69 6e 74 5b 5d 20 ,0];......int[]
0f40: 64 78 3d 5b 30 2c 30 2c 2d 31 2c 2b 31 5d 3b 0a dx=[0,0,-1,+1];.
0f50: 09 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 .....for(int i=0
0f60: 3b 20 69 3c 34 3b 20 2b 2b 69 29 20 7b 0a 09 09 ; i<4; ++i) {...
0f70: 09 09 09 09 69 6e 74 20 79 20 3d 20 70 2e 79 2b ....int y = p.y+
0f80: 64 79 5b 69 5d 3b 0a 09 09 09 09 09 09 69 6e 74 dy[i];.......int
0f90: 20 78 20 3d 20 70 2e 78 2b 64 78 5b 69 5d 3b 0a x = p.x+dx[i];.
0fa0: 09 09 09 09 09 09 69 66 28 76 5b 79 5d 5b 78 5d ......if(v[y][x]
0fb0: 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 ) continue;.....
0fc0: 09 09 69 66 28 79 3d 3d 73 2e 79 20 26 26 20 78 ..if(y==s.y && x
0fd0: 3d 3d 73 2e 78 29 20 7b 0a 09 09 09 09 09 09 09 ==s.x) {........
0fe0: 63 68 61 72 20 63 20 3d 20 22 55 44 52 4c 22 5b char c = "UDRL"[
0ff0: 69 5d 3b 0a 09 09 09 09 09 09 09 69 66 28 20 64 i];........if( d
1000: 65 61 74 68 2e 63 6f 75 6e 74 28 63 29 20 3d 3d eath.count(c) ==
1010: 20 30 20 29 0a 09 09 09 09 09 09 09 09 72 65 74 0 ).........ret
1020: 75 72 6e 20 5b 74 75 70 6c 65 28 63 2c 73 74 65 urn [tuple(c,ste
1030: 70 29 5d 3b 0a 09 09 09 09 09 09 7d 20 65 6c 73 p)];.......} els
1040: 65 20 69 66 28 66 6f 72 62 69 64 64 65 6e 5f 63 e if(forbidden_c
1050: 65 6c 6c 5b 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 ell[y][x]){.....
1060: 09 09 7d 20 65 6c 73 65 20 69 66 28 67 2e 6d 61 ..} else if(g.ma
1070: 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d p[y,x]==' '||g.m
1080: 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 ap[y,x]=='\\'||g
1090: 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 29 20 .map[y,x]=='.')
10a0: 7b 0a 09 09 09 09 09 09 09 71 32 20 7e 3d 20 6e {........q2 ~= n
10b0: 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 ew Pos(y,x);....
10c0: 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 ....v[y][x]=true
10d0: 3b 0a 09 09 09 09 09 09 7d 0a 09 09 09 09 09 7d ;.......}......}
10e0: 0a 09 09 09 09 7d 0a 09 09 09 09 71 20 3d 20 71 .....}.....q = q
10f0: 32 3b 0a 09 09 09 7d 0a 09 09 09 72 65 74 75 72 2;....}....retur
1100: 6e 20 5b 5d 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 n [];...}....//
1110: 70 75 73 68 20 72 6f 63 6b 73 21 0a 09 09 54 75 push rocks!...Tu
1120: 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d ple!(char,int)[]
1130: 20 74 72 79 43 28 29 20 7b 0a 09 09 09 63 6f 6e tryC() {....con
1140: 73 74 28 50 6f 73 29 5b 5d 20 71 3b 0a 09 09 09 st(Pos)[] q;....
1150: 66 6f 72 65 61 63 68 28 70 3b 20 67 73 29 20 71 foreach(p; gs) q
1160: 20 7e 3d 20 70 3b 0a 09 09 09 62 6f 6f 6c 5b 5d ~= p;....bool[]
1170: 5b 5d 20 76 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b [] v = new bool[
1180: 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 ][](g.map.H+2, g
1190: 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 09 66 6f .map.W+2);....fo
11a0: 72 65 61 63 68 28 70 3b 20 71 29 20 76 5b 70 2e reach(p; q) v[p.
11b0: 79 5d 5b 70 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 y][p.x]=true;...
11c0: 09 66 6f 72 28 69 6e 74 20 73 74 65 70 3d 32 30 .for(int step=20
11d0: 3b 20 71 2e 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 ; q.length; ++st
11e0: 65 70 29 20 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 ep) {.....Pos[]
11f0: 71 32 3b 0a 09 09 09 09 66 6f 72 65 61 63 68 28 q2;.....foreach(
1200: 70 3b 20 71 29 20 7b 0a 09 09 09 09 09 69 6e 74 p; q) {......int
1210: 5b 5d 20 64 79 3d 5b 2d 31 2c 2b 31 2c 30 2c 30 [] dy=[-1,+1,0,0
1220: 5d 3b 0a 09 09 09 09 09 69 6e 74 5b 5d 20 64 78 ];......int[] dx
1230: 3d 5b 30 2c 30 2c 2d 31 2c 2b 31 5d 3b 0a 09 09 =[0,0,-1,+1];...
1240: 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
1250: 69 3c 34 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 i<4; ++i) {.....
1260: 09 09 69 6e 74 20 79 20 3d 20 70 2e 79 2b 64 79 ..int y = p.y+dy
1270: 5b 69 5d 3b 0a 09 09 09 09 09 09 69 6e 74 20 78 [i];.......int x
1280: 20 3d 20 70 2e 78 2b 64 78 5b 69 5d 3b 0a 09 09 = p.x+dx[i];...
1290: 09 09 09 09 69 66 28 76 5b 79 5d 5b 78 5d 29 20 ....if(v[y][x])
12a0: 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 continue;.......
12b0: 69 66 28 79 3d 3d 73 2e 79 20 26 26 20 78 3d 3d if(y==s.y && x==
12c0: 73 2e 78 29 20 7b 0a 09 09 09 09 09 09 09 63 68 s.x) {........ch
12d0: 61 72 20 63 20 3d 20 22 55 44 52 4c 22 5b 69 5d ar c = "UDRL"[i]
12e0: 3b 0a 09 09 09 09 09 09 09 69 66 28 20 64 65 61 ;........if( dea
12f0: 74 68 2e 63 6f 75 6e 74 28 63 29 20 3d 3d 20 30 th.count(c) == 0
1300: 20 29 0a 09 09 09 09 09 09 09 09 72 65 74 75 72 ).........retur
1310: 6e 20 5b 74 75 70 6c 65 28 63 2c 73 74 65 70 29 n [tuple(c,step)
1320: 5d 3b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 ];.......} else
1330: 69 66 28 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c if(forbidden_cel
1340: 6c 5b 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 09 09 l[y][x]){.......
1350: 7d 20 65 6c 73 65 20 69 66 28 67 2e 6d 61 70 5b } else if(g.map[
1360: 79 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 y,x]==' '||g.map
1370: 5b 79 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d [y,x]=='\\'||g.m
1380: 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 29 20 7b 0a ap[y,x]=='.') {.
1390: 09 09 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 .......q2 ~= new
13a0: 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 Pos(y,x);......
13b0: 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a ..v[y][x]=true;.
13c0: 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 ......} else if(
13d0: 64 79 5b 69 5d 3d 3d 30 20 26 26 20 67 2e 6d 61 dy[i]==0 && g.ma
13e0: 70 5b 70 5d 3d 3d 27 20 27 20 26 26 20 67 2e 6d p[p]==' ' && g.m
13f0: 61 70 5b 79 2c 78 5d 3d 3d 27 2a 27 20 26 26 20 ap[y,x]=='*' &&
1400: 28 67 2e 6d 61 70 5b 79 2b 64 79 5b 69 5d 2c 78 (g.map[y+dy[i],x
1410: 2b 64 78 5b 69 5d 5d 3d 3d 27 20 27 7c 7c 67 2e +dx[i]]==' '||g.
1420: 6d 61 70 5b 79 2b 64 79 5b 69 5d 2c 78 2b 64 78 map[y+dy[i],x+dx
1430: 5b 69 5d 5d 3d 3d 27 52 27 29 29 20 7b 0a 09 09 [i]]=='R')) {...
1440: 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 50 .....q2 ~= new P
1450: 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 09 os(y,x);........
1460: 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 v[y][x]=true;...
1470: 09 09 09 09 7d 0a 09 09 09 09 09 7d 0a 09 09 09 ....}......}....
1480: 09 7d 0a 09 09 09 09 71 20 3d 20 71 32 3b 0a 09 .}.....q = q2;..
1490: 09 09 7d 0a 09 09 09 72 65 74 75 72 6e 20 5b 5d ..}....return []
14a0: 3b 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e 20 74 ;...}...return t
14b0: 72 79 41 28 29 20 7e 20 74 72 79 42 28 29 20 7e ryA() ~ tryB() ~
14c0: 20 74 72 79 43 28 29 3b 0a 09 7d 0a 7d 0a tryC();..}.}.