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 09 65 6c 73 65 20 69 ice++;....else i
0290: 66 28 20 63 20 21 3d 20 27 57 27 20 29 20 2f 2f f( c != 'W' ) //
02a0: 20 6d 65 61 6e 69 6e 67 6c 65 73 73 20 6d 6f 76 meaningless mov
02b0: 65 0a 09 09 09 09 64 65 61 74 68 20 7e 3d 20 63 e.....death ~= c
02c0: 3b 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e 20 74 ;...}...return t
02d0: 75 70 6c 65 28 64 65 61 74 68 2c 20 63 68 6f 69 uple(death, choi
02e0: 63 65 29 3b 0a 09 7d 0a 0a 09 54 75 70 6c 65 21 ce);..}...Tuple!
02f0: 28 50 6f 73 2c 20 69 6e 74 29 5b 5d 20 6c 6f 67 (Pos, int)[] log
0300: 3b 0a 09 62 6f 6f 6c 5b 5d 5b 5d 20 66 6f 72 62 ;..bool[][] forb
0310: 69 64 64 65 6e 5f 63 65 6c 6c 3b 0a 0a 09 63 68 idden_cell;...ch
0320: 61 72 20 61 63 74 28 63 6f 6e 73 74 28 47 61 6d ar act(const(Gam
0330: 65 29 20 67 2c 20 73 74 72 69 6e 67 20 64 65 61 e) g, string dea
0340: 74 68 2c 20 69 6e 74 20 62 72 65 61 74 68 29 0a th, int breath).
0350: 09 7b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 20 20 .{...const Pos
0360: 20 72 6f 20 3d 20 67 2e 6d 61 70 2e 72 6f 62 6f ro = g.map.robo
0370: 74 3b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 5b 5d t;...const Pos[]
0380: 20 6c 61 20 3d 20 67 2e 6d 61 70 2e 6c 61 6d 62 la = g.map.lamb
0390: 64 61 73 28 29 3b 0a 09 09 63 6f 6e 73 74 20 50 das();...const P
03a0: 6f 73 20 20 20 6c 69 20 3d 20 67 2e 6d 61 70 2e os li = g.map.
03b0: 6c 69 66 74 3b 0a 0a 09 09 54 75 70 6c 65 21 28 lift;....Tuple!(
03c0: 63 68 61 72 2c 69 6e 74 29 5b 5d 20 63 61 6e 64 char,int)[] cand
03d0: 3b 0a 09 09 63 68 61 72 20 63 20 3d 20 27 57 27 ;...char c = 'W'
03e0: 3b 0a 09 09 69 66 28 20 6c 61 2e 65 6d 70 74 79 ;...if( la.empty
03f0: 20 29 20 7b 0a 09 09 09 63 61 6e 64 20 3d 20 73 ) {....cand = s
0400: 65 61 72 63 68 28 67 2c 20 72 6f 2c 20 5b 6c 69 earch(g, ro, [li
0410: 5d 2c 20 64 65 61 74 68 29 3b 0a 09 09 7d 20 65 ], death);...} e
0420: 6c 73 65 20 7b 0a 09 09 09 63 61 6e 64 20 7e 3d lse {....cand ~=
0430: 20 73 65 61 72 63 68 28 67 2c 20 72 6f 2c 20 6c search(g, ro, l
0440: 61 2c 20 64 65 61 74 68 29 3b 0a 09 09 7d 0a 0a a, death);...}..
0450: 09 09 2f 2f 20 27 64 69 67 27 20 6d 6f 64 65 0a ..// 'dig' mode.
0460: 09 09 69 66 28 63 61 6e 64 2e 65 6d 70 74 79 29 ..if(cand.empty)
0470: 20 7b 0a 09 09 09 63 6f 6e 73 74 28 50 6f 73 29 {....const(Pos)
0480: 5b 5d 20 74 67 74 3b 0a 09 09 09 66 6f 72 28 69 [] tgt;....for(i
0490: 6e 74 20 79 3d 31 3b 20 79 3c 3d 67 2e 6d 61 70 nt y=1; y<=g.map
04a0: 2e 48 3b 20 2b 2b 79 29 0a 09 09 09 66 6f 72 28 .H; ++y)....for(
04b0: 69 6e 74 20 78 3d 31 3b 20 78 3c 3d 67 2e 6d 61 int x=1; x<=g.ma
04c0: 70 2e 57 3b 20 2b 2b 78 29 0a 09 09 09 09 69 66 p.W; ++x).....if
04d0: 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 (g.map[y,x]=='.'
04e0: 29 0a 09 09 09 09 09 69 66 28 67 2e 6d 61 70 5b )......if(g.map[
04f0: 79 2b 31 2c 78 5d 3d 3d 27 2a 27 7c 7c 67 2e 6d y+1,x]=='*'||g.m
0500: 61 70 5b 79 2b 31 2c 78 2d 31 5d 3d 3d 27 2a 27 ap[y+1,x-1]=='*'
0510: 7c 7c 67 2e 6d 61 70 5b 79 2b 31 2c 78 2b 31 5d ||g.map[y+1,x+1]
0520: 3d 3d 27 2a 27 0a 09 09 09 09 09 20 7c 7c 67 2e =='*'...... ||g.
0530: 6d 61 70 5b 79 2c 78 2b 31 5d 3d 3d 27 2a 27 7c map[y,x+1]=='*'|
0540: 7c 67 2e 6d 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27 |g.map[y,x-1]=='
0550: 2a 27 29 0a 09 09 09 09 09 09 74 67 74 20 7e 3d *').......tgt ~=
0560: 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 new Pos(y,x);..
0570: 09 09 63 61 6e 64 20 7e 3d 20 73 65 61 72 63 68 ..cand ~= search
0580: 28 67 2c 20 72 6f 2c 20 74 67 74 2c 20 64 65 61 (g, ro, tgt, dea
0590: 74 68 2c 20 74 72 75 65 29 3b 0a 09 09 7d 0a 0a th, true);...}..
05a0: 09 09 69 66 28 63 61 6e 64 2e 65 6d 70 74 79 29 ..if(cand.empty)
05b0: 0a 09 09 09 63 61 6e 64 20 7e 3d 20 74 75 70 6c ....cand ~= tupl
05c0: 65 28 27 57 27 2c 69 6e 74 2e 6d 61 78 29 3b 0a e('W',int.max);.
05d0: 09 09 73 6f 72 74 21 28 28 54 75 70 6c 65 21 28 ..sort!((Tuple!(
05e0: 63 68 61 72 2c 69 6e 74 29 20 63 31 2c 20 54 75 char,int) c1, Tu
05f0: 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 20 63 ple!(char,int) c
0600: 32 29 7b 0a 09 09 09 69 66 28 63 31 5b 31 5d 20 2){....if(c1[1]
0610: 21 3d 20 63 32 5b 31 5d 29 0a 09 09 09 09 72 65 != c2[1]).....re
0620: 74 75 72 6e 20 63 31 5b 31 5d 20 3c 20 63 32 5b turn c1[1] < c2[
0630: 31 5d 3b 0a 09 09 09 72 65 74 75 72 6e 20 63 31 1];....return c1
0640: 5b 30 5d 20 3c 20 63 32 5b 30 5d 3b 0a 09 09 7d [0] < c2[0];...}
0650: 29 28 63 61 6e 64 29 3b 0a 09 09 63 20 3d 20 63 )(cand);...c = c
0660: 61 6e 64 5b 30 5d 5b 30 5d 3b 0a 0a 09 09 69 66 and[0][0];....if
0670: 28 64 65 61 74 68 2e 63 6f 75 6e 74 28 63 29 20 (death.count(c)
0680: 7c 7c 20 77 61 69 74 5f 63 6f 75 6e 74 3e 3d 32 || wait_count>=2
0690: 29 20 7b 0a 09 09 09 66 6f 72 65 61 63 68 28 63 ) {....foreach(c
06a0: 68 61 72 20 6c 69 76 65 3b 20 22 55 44 4c 52 57 har live; "UDLRW
06b0: 22 29 0a 09 09 09 09 69 66 28 64 65 61 74 68 2e ").....if(death.
06c0: 63 6f 75 6e 74 28 6c 69 76 65 29 3d 3d 30 29 20 count(live)==0)
06d0: 7b 0a 09 09 09 09 09 63 3d 6c 69 76 65 3b 0a 09 {......c=live;..
06e0: 09 09 09 09 62 72 65 61 6b 3b 0a 09 09 09 09 7d ....break;.....}
06f0: 0a 09 09 7d 0a 0a 09 09 69 66 28 63 3d 3d 27 57 ...}....if(c=='W
0700: 27 29 20 7b 0a 09 09 09 77 61 69 74 5f 63 6f 75 ') {....wait_cou
0710: 6e 74 2b 2b 3b 0a 09 09 09 69 66 28 77 61 69 74 nt++;....if(wait
0720: 5f 63 6f 75 6e 74 20 3e 20 67 2e 6d 61 70 2e 48 _count > g.map.H
0730: 29 0a 09 09 09 09 63 20 3d 20 27 41 27 3b 0a 09 ).....c = 'A';..
0740: 09 7d 0a 09 09 65 6c 73 65 0a 09 09 09 77 61 69 .}...else....wai
0750: 74 5f 63 6f 75 6e 74 20 3d 20 30 3b 0a 0a 09 09 t_count = 0;....
0760: 62 6f 6f 6c 5b 63 68 61 72 5d 20 63 68 6f 69 63 bool[char] choic
0770: 65 3b 0a 09 09 66 6f 72 65 61 63 68 28 74 3b 20 e;...foreach(t;
0780: 63 61 6e 64 29 0a 09 09 09 63 68 6f 69 63 65 5b cand)....choice[
0790: 74 5b 30 5d 5d 20 3d 20 74 72 75 65 3b 0a 09 09 t[0]] = true;...
07a0: 6c 6f 67 20 7e 3d 20 74 75 70 6c 65 28 72 6f 2e log ~= tuple(ro.
07b0: 63 6c 6f 6e 65 28 29 2c 20 63 61 73 74 28 69 6e clone(), cast(in
07c0: 74 29 63 68 6f 69 63 65 2e 6c 65 6e 67 74 68 29 t)choice.length)
07d0: 3b 0a 09 09 69 66 28 6c 6f 67 2e 6c 65 6e 67 74 ;...if(log.lengt
07e0: 68 20 3e 20 35 29 0a 09 09 09 6c 6f 67 20 3d 20 h > 5)....log =
07f0: 6c 6f 67 5b 24 2d 35 2e 2e 24 5d 3b 0a 09 09 69 log[$-5..$];...i
0800: 6e 74 20 63 6e 74 20 3d 20 30 3b 0a 09 09 66 6f nt cnt = 0;...fo
0810: 72 65 61 63 68 28 6c 3b 20 6c 6f 67 29 0a 09 09 reach(l; log)...
0820: 09 69 66 28 6c 5b 30 5d 20 3d 3d 20 6c 6f 67 5b .if(l[0] == log[
0830: 24 2d 31 5d 5b 30 5d 29 0a 09 09 09 09 2b 2b 63 $-1][0]).....++c
0840: 6e 74 3b 0a 09 09 69 66 28 20 63 6e 74 20 3e 3d nt;...if( cnt >=
0850: 20 33 20 26 26 20 62 72 65 61 74 68 3d 3d 31 20 3 && breath==1
0860: 29 20 7b 0a 09 09 09 66 6f 72 62 69 64 64 65 6e ) {....forbidden
0870: 5f 63 65 6c 6c 5b 72 6f 2e 79 5d 5b 72 6f 2e 78 _cell[ro.y][ro.x
0880: 5d 20 3d 20 74 72 75 65 3b 0a 09 09 7d 0a 0a 09 ] = true;...}...
0890: 09 72 65 74 75 72 6e 20 63 3b 0a 09 7d 0a 0a 09 .return c;..}...
08a0: 54 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 Tuple!(char,int)
08b0: 5b 5d 20 73 65 61 72 63 68 28 69 6e 20 47 61 6d [] search(in Gam
08c0: 65 20 67 2c 20 69 6e 20 50 6f 73 20 73 2c 20 69 e g, in Pos s, i
08d0: 6e 20 50 6f 73 5b 5d 20 67 73 2c 20 73 74 72 69 n Pos[] gs, stri
08e0: 6e 67 20 64 65 61 74 68 2c 20 62 6f 6f 6c 20 64 ng death, bool d
08f0: 61 6e 67 65 72 5f 6f 6b 3d 66 61 6c 73 65 29 0a anger_ok=false).
0900: 09 7b 0a 09 09 62 6f 6f 6c 20 64 61 6e 67 65 72 .{...bool danger
0910: 28 69 6e 74 20 79 2c 20 69 6e 74 20 78 29 0a 09 (int y, int x)..
0920: 09 7b 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 .{....if(g.map[y
0930: 2c 78 5d 20 3d 3d 20 27 20 27 20 7c 7c 20 67 2e ,x] == ' ' || g.
0940: 6d 61 70 5b 79 2c 78 5d 20 3d 3d 20 27 52 27 29 map[y,x] == 'R')
0950: 0a 09 09 09 09 72 65 74 75 72 6e 20 66 61 6c 73 .....return fals
0960: 65 3b 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 e;....if(g.map[y
0970: 2b 31 2c 78 5d 20 3d 3d 20 27 2a 27 29 0a 09 09 +1,x] == '*')...
0980: 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b 0a 09 ..return true;..
0990: 09 09 69 66 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 ..if(g.map[y+1,x
09a0: 2d 31 5d 3d 3d 27 2a 27 20 26 26 20 28 67 2e 6d -1]=='*' && (g.m
09b0: 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27 5c 5c 27 7c ap[y,x-1]=='\\'|
09c0: 7c 67 2e 6d 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27 |g.map[y,x-1]=='
09d0: 2a 27 29 20 26 26 20 28 67 2e 6d 61 70 5b 79 2b *') && (g.map[y+
09e0: 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 1,x]==' '||g.map
09f0: 5b 79 2b 31 2c 78 5d 3d 3d 27 52 27 29 29 0a 09 [y+1,x]=='R'))..
0a00: 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b 0a ...return true;.
0a10: 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2b 31 2c ...if(g.map[y+1,
0a20: 78 2b 31 5d 3d 3d 27 2a 27 20 26 26 20 28 67 2e x+1]=='*' && (g.
0a30: 6d 61 70 5b 79 2c 78 2b 31 5d 3d 3d 27 2a 27 29 map[y,x+1]=='*')
0a40: 20 26 26 20 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 && (g.map[y+1,x
0a50: 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2b ]==' '||g.map[y+
0a60: 31 2c 78 5d 3d 3d 27 52 27 29 29 0a 09 09 09 09 1,x]=='R')).....
0a70: 72 65 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 return true;....
0a80: 69 66 28 67 2e 6d 61 70 5b 79 2c 78 2d 31 5d 3d if(g.map[y,x-1]=
0a90: 3d 27 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 ='*' && (g.map[y
0aa0: 2d 31 2c 78 2d 31 5d 3d 3d 27 5c 5c 27 7c 7c 67 -1,x-1]=='\\'||g
0ab0: 2e 6d 61 70 5b 79 2d 31 2c 78 2d 31 5d 3d 3d 27 .map[y-1,x-1]=='
0ac0: 2a 27 29 20 26 26 20 28 67 2e 6d 61 70 5b 79 2d *') && (g.map[y-
0ad0: 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 1,x]==' '||g.map
0ae0: 5b 79 2d 31 2c 78 5d 3d 3d 27 52 27 29 29 0a 09 [y-1,x]=='R'))..
0af0: 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b 0a ...return true;.
0b00: 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2c 78 2b ...if(g.map[y,x+
0b10: 31 5d 3d 3d 27 2a 27 20 26 26 20 28 67 2e 6d 61 1]=='*' && (g.ma
0b20: 70 5b 79 2d 31 2c 78 2b 31 5d 3d 3d 27 2a 27 29 p[y-1,x+1]=='*')
0b30: 20 26 26 20 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 && (g.map[y-1,x
0b40: 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2d ]==' '||g.map[y-
0b50: 31 2c 78 5d 3d 3d 27 52 27 29 29 0a 09 09 09 09 1,x]=='R')).....
0b60: 72 65 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 return true;....
0b70: 72 65 74 75 72 6e 20 66 61 6c 73 65 3b 0a 09 09 return false;...
0b80: 7d 0a 0a 09 09 2f 2f 20 61 76 6f 69 64 20 64 69 }....// avoid di
0b90: 72 65 63 74 6c 79 20 62 65 6c 6f 77 20 27 2a 27 rectly below '*'
0ba0: 0a 09 09 54 75 70 6c 65 21 28 63 68 61 72 2c 69 ...Tuple!(char,i
0bb0: 6e 74 29 5b 5d 20 74 72 79 41 28 29 20 7b 0a 09 nt)[] tryA() {..
0bc0: 09 09 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 71 ..const(Pos)[] q
0bd0: 3b 0a 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 ;....foreach(p;
0be0: 67 73 29 0a 09 09 09 09 69 66 28 21 64 61 6e 67 gs).....if(!dang
0bf0: 65 72 28 70 2e 79 2c 70 2e 78 29 29 0a 09 09 09 er(p.y,p.x))....
0c00: 09 09 71 20 7e 3d 20 70 3b 0a 09 09 09 62 6f 6f ..q ~= p;....boo
0c10: 6c 5b 5d 5b 5d 20 76 20 3d 20 6e 65 77 20 62 6f l[][] v = new bo
0c20: 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 ol[][](g.map.H+2
0c30: 2c 20 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 , g.map.W+2);...
0c40: 09 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 76 .foreach(p; q) v
0c50: 5b 70 2e 79 5d 5b 70 2e 78 5d 3d 74 72 75 65 3b [p.y][p.x]=true;
0c60: 0a 09 09 09 66 6f 72 28 69 6e 74 20 73 74 65 70 ....for(int step
0c70: 3d 31 3b 20 71 2e 6c 65 6e 67 74 68 3b 20 2b 2b =1; q.length; ++
0c80: 73 74 65 70 29 20 7b 0a 09 09 09 09 50 6f 73 5b step) {.....Pos[
0c90: 5d 20 71 32 3b 0a 09 09 09 09 66 6f 72 65 61 63 ] q2;.....foreac
0ca0: 68 28 70 3b 20 71 29 20 7b 0a 09 09 09 09 09 69 h(p; q) {......i
0cb0: 6e 74 5b 5d 20 79 79 79 3d 5b 70 2e 79 2d 31 2c nt[] yyy=[p.y-1,
0cc0: 70 2e 79 2b 31 2c 70 2e 79 2c 70 2e 79 5d 3b 0a p.y+1,p.y,p.y];.
0cd0: 09 09 09 09 09 69 6e 74 5b 5d 20 78 78 78 3d 5b .....int[] xxx=[
0ce0: 70 2e 78 2c 70 2e 78 2c 70 2e 78 2d 31 2c 70 2e p.x,p.x,p.x-1,p.
0cf0: 78 2b 31 5d 3b 0a 09 09 09 09 09 66 6f 72 28 69 x+1];......for(i
0d00: 6e 74 20 69 3d 30 3b 20 69 3c 79 79 79 2e 6c 65 nt i=0; i<yyy.le
0d10: 6e 67 74 68 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 ngth; ++i) {....
0d20: 09 09 09 69 6e 74 20 79 20 3d 20 79 79 79 5b 69 ...int y = yyy[i
0d30: 5d 3b 0a 09 09 09 09 09 09 69 6e 74 20 78 20 3d ];.......int x =
0d40: 20 78 78 78 5b 69 5d 3b 0a 09 09 09 09 09 09 69 xxx[i];.......i
0d50: 66 28 27 31 27 3c 3d 67 2e 6d 61 70 5b 79 2c 78 f('1'<=g.map[y,x
0d60: 5d 26 26 67 2e 6d 61 70 5b 79 2c 78 5d 3c 3d 27 ]&&g.map[y,x]<='
0d70: 39 27 29 20 7b 0a 09 09 09 09 09 09 09 66 6f 72 9') {........for
0d80: 65 61 63 68 28 70 70 70 3b 20 67 2e 6d 61 70 2e each(ppp; g.map.
0d90: 74 72 5f 73 6f 75 72 63 65 5b 67 2e 6d 61 70 5b tr_source[g.map[
0da0: 79 2c 78 5d 5d 29 20 7b 0a 09 09 09 09 09 09 09 y,x]]) {........
0db0: 09 79 79 79 20 7e 3d 20 70 70 70 2e 79 3b 0a 09 .yyy ~= ppp.y;..
0dc0: 09 09 09 09 09 09 09 78 78 78 20 7e 3d 20 70 70 .......xxx ~= pp
0dd0: 70 2e 78 3b 0a 09 09 09 09 09 09 09 7d 0a 09 09 p.x;........}...
0de0: 09 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0a 09 .....continue;..
0df0: 09 09 09 09 09 7d 0a 09 09 09 09 09 09 69 66 28 .....}.......if(
0e00: 76 5b 79 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e 75 v[y][x]) continu
0e10: 65 3b 0a 09 09 09 09 09 09 69 66 28 79 3d 3d 73 e;.......if(y==s
0e20: 2e 79 20 26 26 20 78 3d 3d 73 2e 78 20 26 26 20 .y && x==s.x &&
0e30: 69 3c 34 29 20 7b 0a 09 09 09 09 09 09 09 63 68 i<4) {........ch
0e40: 61 72 20 63 20 3d 20 22 55 44 52 4c 22 5b 69 5d ar c = "UDRL"[i]
0e50: 3b 0a 09 09 09 09 09 09 09 69 66 28 20 64 65 61 ;........if( dea
0e60: 74 68 2e 63 6f 75 6e 74 28 63 29 20 3d 3d 20 30 th.count(c) == 0
0e70: 20 29 0a 09 09 09 09 09 09 09 09 72 65 74 75 72 ).........retur
0e80: 6e 20 5b 74 75 70 6c 65 28 63 2c 73 74 65 70 29 n [tuple(c,step)
0e90: 5d 3b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 ];.......} else
0ea0: 69 66 28 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c if(forbidden_cel
0eb0: 6c 5b 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 09 09 l[y][x]){.......
0ec0: 7d 20 65 6c 73 65 20 69 66 28 67 2e 6d 61 70 5b } else if(g.map[
0ed0: 79 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 y,x]==' '||g.map
0ee0: 5b 79 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d [y,x]=='\\'||g.m
0ef0: 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 7c 7c 69 3e ap[y,x]=='.'||i>
0f00: 3d 34 29 20 7b 0a 09 09 09 09 09 09 09 69 66 28 =4) {........if(
0f10: 64 61 6e 67 65 72 28 79 2c 78 29 29 0a 09 09 09 danger(y,x))....
0f20: 09 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0a 09 .....continue;..
0f30: 09 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 ......q2 ~= new
0f40: 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 Pos(y,x);.......
0f50: 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 .v[y][x]=true;..
0f60: 09 09 09 09 09 7d 0a 09 09 09 09 09 7d 0a 09 09 .....}......}...
0f70: 09 09 7d 0a 09 09 09 09 71 20 3d 20 71 32 3b 0a ..}.....q = q2;.
0f80: 09 09 09 7d 0a 09 09 09 72 65 74 75 72 6e 20 5b ...}....return [
0f90: 5d 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 61 6e 79 ];...}....// any
0fa0: 20 65 6d 70 74 79 20 73 70 61 63 65 20 69 73 20 empty space is
0fb0: 6d 79 20 67 72 6f 75 6e 64 0a 09 09 54 75 70 6c my ground...Tupl
0fc0: 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d 20 74 e!(char,int)[] t
0fd0: 72 79 42 28 29 20 7b 0a 09 09 09 63 6f 6e 73 74 ryB() {....const
0fe0: 28 50 6f 73 29 5b 5d 20 71 3b 0a 09 09 09 66 6f (Pos)[] q;....fo
0ff0: 72 65 61 63 68 28 70 3b 20 67 73 29 20 71 20 7e reach(p; gs) q ~
1000: 3d 20 70 3b 0a 09 09 09 62 6f 6f 6c 5b 5d 5b 5d = p;....bool[][]
1010: 20 76 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b v = new bool[][
1020: 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d ](g.map.H+2, g.m
1030: 61 70 2e 57 2b 32 29 3b 0a 09 09 09 66 6f 72 65 ap.W+2);....fore
1040: 61 63 68 28 70 3b 20 71 29 20 76 5b 70 2e 79 5d ach(p; q) v[p.y]
1050: 5b 70 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 09 66 [p.x]=true;....f
1060: 6f 72 28 69 6e 74 20 73 74 65 70 3d 31 30 3b 20 or(int step=10;
1070: 71 2e 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 q.length; ++step
1080: 29 20 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 71 32 ) {.....Pos[] q2
1090: 3b 0a 09 09 09 09 66 6f 72 65 61 63 68 28 70 3b ;.....foreach(p;
10a0: 20 71 29 20 7b 0a 09 09 09 09 09 69 6e 74 5b 5d q) {......int[]
10b0: 20 79 79 79 3d 5b 70 2e 79 2d 31 2c 70 2e 79 2b yyy=[p.y-1,p.y+
10c0: 31 2c 70 2e 79 2c 70 2e 79 5d 3b 0a 09 09 09 09 1,p.y,p.y];.....
10d0: 09 69 6e 74 5b 5d 20 78 78 78 3d 5b 70 2e 78 2c .int[] xxx=[p.x,
10e0: 70 2e 78 2c 70 2e 78 2d 31 2c 70 2e 78 2b 31 5d p.x,p.x-1,p.x+1]
10f0: 3b 0a 09 09 09 09 09 66 6f 72 28 69 6e 74 20 69 ;......for(int i
1100: 3d 30 3b 20 69 3c 79 79 79 2e 6c 65 6e 67 74 68 =0; i<yyy.length
1110: 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 09 69 ; ++i) {.......i
1120: 6e 74 20 79 20 3d 20 79 79 79 5b 69 5d 3b 0a 09 nt y = yyy[i];..
1130: 09 09 09 09 09 69 6e 74 20 78 20 3d 20 78 78 78 .....int x = xxx
1140: 5b 69 5d 3b 0a 09 09 09 09 09 09 69 66 28 27 31 [i];.......if('1
1150: 27 3c 3d 67 2e 6d 61 70 5b 79 2c 78 5d 26 26 67 '<=g.map[y,x]&&g
1160: 2e 6d 61 70 5b 79 2c 78 5d 3c 3d 27 39 27 29 20 .map[y,x]<='9')
1170: 7b 0a 09 09 09 09 09 09 09 66 6f 72 65 61 63 68 {........foreach
1180: 28 70 70 70 3b 20 67 2e 6d 61 70 2e 74 72 5f 73 (ppp; g.map.tr_s
1190: 6f 75 72 63 65 5b 67 2e 6d 61 70 5b 79 2c 78 5d ource[g.map[y,x]
11a0: 5d 29 20 7b 0a 09 09 09 09 09 09 09 09 79 79 79 ]) {.........yyy
11b0: 20 7e 3d 20 70 70 70 2e 79 3b 0a 09 09 09 09 09 ~= ppp.y;......
11c0: 09 09 09 78 78 78 20 7e 3d 20 70 70 70 2e 78 3b ...xxx ~= ppp.x;
11d0: 0a 09 09 09 09 09 09 09 7d 0a 09 09 09 09 09 09 ........}.......
11e0: 09 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 .continue;......
11f0: 09 7d 0a 09 09 09 09 09 09 69 66 28 76 5b 79 5d .}.......if(v[y]
1200: 5b 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 [x]) continue;..
1210: 09 09 09 09 09 69 66 28 79 3d 3d 73 2e 79 20 26 .....if(y==s.y &
1220: 26 20 78 3d 3d 73 2e 78 20 26 26 20 69 3c 34 29 & x==s.x && i<4)
1230: 20 7b 0a 09 09 09 09 09 09 09 63 68 61 72 20 63 {........char c
1240: 20 3d 20 22 55 44 52 4c 22 5b 69 5d 3b 0a 09 09 = "UDRL"[i];...
1250: 09 09 09 09 09 69 66 28 20 64 65 61 74 68 2e 63 .....if( death.c
1260: 6f 75 6e 74 28 63 29 20 3d 3d 20 30 20 29 0a 09 ount(c) == 0 )..
1270: 09 09 09 09 09 09 09 72 65 74 75 72 6e 20 5b 74 .......return [t
1280: 75 70 6c 65 28 63 2c 73 74 65 70 29 5d 3b 0a 09 uple(c,step)];..
1290: 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 66 .....} else if(f
12a0: 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 5b 79 5d orbidden_cell[y]
12b0: 5b 78 5d 29 7b 0a 09 09 09 09 09 09 7d 20 65 6c [x]){.......} el
12c0: 73 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d se if(g.map[y,x]
12d0: 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 ==' '||g.map[y,x
12e0: 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 ]=='\\'||g.map[y
12f0: 2c 78 5d 3d 3d 27 2e 27 7c 7c 69 3e 3d 34 29 20 ,x]=='.'||i>=4)
1300: 7b 0a 09 09 09 09 09 09 09 71 32 20 7e 3d 20 6e {........q2 ~= n
1310: 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 ew Pos(y,x);....
1320: 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 ....v[y][x]=true
1330: 3b 0a 09 09 09 09 09 09 7d 0a 09 09 09 09 09 7d ;.......}......}
1340: 0a 09 09 09 09 7d 0a 09 09 09 09 71 20 3d 20 71 .....}.....q = q
1350: 32 3b 0a 09 09 09 7d 0a 09 09 09 72 65 74 75 72 2;....}....retur
1360: 6e 20 5b 5d 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 n [];...}....//
1370: 70 75 73 68 20 72 6f 63 6b 73 21 0a 09 09 54 75 push rocks!...Tu
1380: 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d ple!(char,int)[]
1390: 20 74 72 79 43 28 29 20 7b 0a 09 09 09 63 6f 6e tryC() {....con
13a0: 73 74 28 50 6f 73 29 5b 5d 20 71 3b 0a 09 09 09 st(Pos)[] q;....
13b0: 66 6f 72 65 61 63 68 28 70 3b 20 67 73 29 20 71 foreach(p; gs) q
13c0: 20 7e 3d 20 70 3b 0a 09 09 09 62 6f 6f 6c 5b 5d ~= p;....bool[]
13d0: 5b 5d 20 76 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b [] v = new bool[
13e0: 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 ][](g.map.H+2, g
13f0: 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 09 66 6f .map.W+2);....fo
1400: 72 65 61 63 68 28 70 3b 20 71 29 20 76 5b 70 2e reach(p; q) v[p.
1410: 79 5d 5b 70 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 y][p.x]=true;...
1420: 09 66 6f 72 28 69 6e 74 20 73 74 65 70 3d 32 30 .for(int step=20
1430: 3b 20 71 2e 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 ; q.length; ++st
1440: 65 70 29 20 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 ep) {.....Pos[]
1450: 71 32 3b 0a 09 09 09 09 66 6f 72 65 61 63 68 28 q2;.....foreach(
1460: 70 3b 20 71 29 20 7b 0a 09 09 09 09 09 69 6e 74 p; q) {......int
1470: 5b 5d 20 79 79 79 3d 5b 70 2e 79 2d 31 2c 70 2e [] yyy=[p.y-1,p.
1480: 79 2b 31 2c 70 2e 79 2c 70 2e 79 5d 3b 0a 09 09 y+1,p.y,p.y];...
1490: 09 09 09 69 6e 74 5b 5d 20 78 78 78 3d 5b 70 2e ...int[] xxx=[p.
14a0: 78 2c 70 2e 78 2c 70 2e 78 2d 31 2c 70 2e 78 2b x,p.x,p.x-1,p.x+
14b0: 31 5d 3b 0a 09 09 09 09 09 66 6f 72 28 69 6e 74 1];......for(int
14c0: 20 69 3d 30 3b 20 69 3c 79 79 79 2e 6c 65 6e 67 i=0; i<yyy.leng
14d0: 74 68 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 th; ++i) {......
14e0: 09 69 6e 74 20 79 20 3d 20 79 79 79 5b 69 5d 3b .int y = yyy[i];
14f0: 0a 09 09 09 09 09 09 69 6e 74 20 78 20 3d 20 78 .......int x = x
1500: 78 78 5b 69 5d 3b 0a 09 09 09 09 09 09 69 66 28 xx[i];.......if(
1510: 27 31 27 3c 3d 67 2e 6d 61 70 5b 79 2c 78 5d 26 '1'<=g.map[y,x]&
1520: 26 67 2e 6d 61 70 5b 79 2c 78 5d 3c 3d 27 39 27 &g.map[y,x]<='9'
1530: 29 20 7b 0a 09 09 09 09 09 09 09 66 6f 72 65 61 ) {........forea
1540: 63 68 28 70 70 70 3b 20 67 2e 6d 61 70 2e 74 72 ch(ppp; g.map.tr
1550: 5f 73 6f 75 72 63 65 5b 67 2e 6d 61 70 5b 79 2c _source[g.map[y,
1560: 78 5d 5d 29 20 7b 0a 09 09 09 09 09 09 09 09 79 x]]) {.........y
1570: 79 79 20 7e 3d 20 70 70 70 2e 79 3b 0a 09 09 09 yy ~= ppp.y;....
1580: 09 09 09 09 09 78 78 78 20 7e 3d 20 70 70 70 2e .....xxx ~= ppp.
1590: 78 3b 0a 09 09 09 09 09 09 09 7d 0a 09 09 09 09 x;........}.....
15a0: 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 ...continue;....
15b0: 09 09 09 7d 0a 09 09 09 09 09 09 69 66 28 76 5b ...}.......if(v[
15c0: 79 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b y][x]) continue;
15d0: 0a 09 09 09 09 09 09 69 66 28 79 3d 3d 73 2e 79 .......if(y==s.y
15e0: 20 26 26 20 78 3d 3d 73 2e 78 20 26 26 20 69 3c && x==s.x && i<
15f0: 34 29 20 7b 0a 09 09 09 09 09 09 09 63 68 61 72 4) {........char
1600: 20 63 20 3d 20 22 55 44 52 4c 22 5b 69 5d 3b 0a c = "UDRL"[i];.
1610: 09 09 09 09 09 09 09 69 66 28 20 64 65 61 74 68 .......if( death
1620: 2e 63 6f 75 6e 74 28 63 29 20 3d 3d 20 30 20 29 .count(c) == 0 )
1630: 0a 09 09 09 09 09 09 09 09 72 65 74 75 72 6e 20 .........return
1640: 5b 74 75 70 6c 65 28 63 2c 73 74 65 70 29 5d 3b [tuple(c,step)];
1650: 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 .......} else if
1660: 28 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 5b (forbidden_cell[
1670: 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 09 09 7d 20 y][x]){.......}
1680: 65 6c 73 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c else if(g.map[y,
1690: 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 x]==' '||g.map[y
16a0: 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 ,x]=='\\'||g.map
16b0: 5b 79 2c 78 5d 3d 3d 27 2e 27 7c 7c 69 3e 3d 34 [y,x]=='.'||i>=4
16c0: 29 20 7b 0a 09 09 09 09 09 09 09 71 32 20 7e 3d ) {........q2 ~=
16d0: 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 new Pos(y,x);..
16e0: 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 ......v[y][x]=tr
16f0: 75 65 3b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 ue;.......} else
1700: 20 69 66 28 69 3c 34 20 26 26 20 28 79 2d 70 2e if(i<4 && (y-p.
1710: 79 29 3d 3d 30 20 26 26 20 67 2e 6d 61 70 5b 70 y)==0 && g.map[p
1720: 5d 3d 3d 27 20 27 20 26 26 20 67 2e 6d 61 70 5b ]==' ' && g.map[
1730: 79 2c 78 5d 3d 3d 27 2a 27 20 26 26 20 28 67 2e y,x]=='*' && (g.
1740: 6d 61 70 5b 79 2b 28 79 2d 70 2e 79 29 2c 78 2b map[y+(y-p.y),x+
1750: 28 78 2d 70 2e 78 29 5d 3d 3d 27 20 27 7c 7c 67 (x-p.x)]==' '||g
1760: 2e 6d 61 70 5b 79 2b 28 79 2d 70 2e 79 29 2c 78 .map[y+(y-p.y),x
1770: 2b 28 78 2d 70 2e 78 29 5d 3d 3d 27 52 27 29 29 +(x-p.x)]=='R'))
1780: 20 7b 0a 09 09 09 09 09 09 09 71 32 20 7e 3d 20 {........q2 ~=
1790: 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 new Pos(y,x);...
17a0: 09 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 .....v[y][x]=tru
17b0: 65 3b 0a 09 09 09 09 09 09 7d 0a 09 09 09 09 09 e;.......}......
17c0: 7d 0a 09 09 09 09 7d 0a 09 09 09 09 71 20 3d 20 }.....}.....q =
17d0: 71 32 3b 0a 09 09 09 7d 0a 09 09 09 72 65 74 75 q2;....}....retu
17e0: 72 6e 20 5b 5d 3b 0a 09 09 7d 0a 09 09 72 65 74 rn [];...}...ret
17f0: 75 72 6e 20 28 64 61 6e 67 65 72 5f 6f 6b 20 3f urn (danger_ok ?
1800: 20 5b 5d 20 3a 20 74 72 79 41 28 29 29 20 7e 20 [] : tryA()) ~
1810: 74 72 79 42 28 29 20 7e 20 74 72 79 43 28 29 3b tryB() ~ tryC();
1820: 0a 09 7d 0a 7d 0a 0a 61 6c 69 61 73 20 53 6f 6c ..}.}..alias Sol
1830: 76 65 72 5f 31 20 4d 61 69 6e 53 6f 6c 76 65 72 ver_1 MainSolver
1840: 3b 0a ;.