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 63 61 6e 64 20 7e 3d 20 74 75 ..}...cand ~= tu
0420: 70 6c 65 28 27 57 27 2c 69 6e 74 2e 6d 61 78 29 ple('W',int.max)
0430: 3b 0a 09 09 73 6f 72 74 21 28 28 54 75 70 6c 65 ;...sort!((Tuple
0440: 21 28 63 68 61 72 2c 69 6e 74 29 20 63 31 2c 20 !(char,int) c1,
0450: 54 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 Tuple!(char,int)
0460: 20 63 32 29 7b 0a 09 09 09 69 66 28 63 31 5b 31 c2){....if(c1[1
0470: 5d 20 21 3d 20 63 32 5b 31 5d 29 0a 09 09 09 09 ] != c2[1]).....
0480: 72 65 74 75 72 6e 20 63 31 5b 31 5d 20 3c 20 63 return c1[1] < c
0490: 32 5b 31 5d 3b 0a 09 09 09 72 65 74 75 72 6e 20 2[1];....return
04a0: 63 31 5b 30 5d 20 3c 20 63 32 5b 30 5d 3b 0a 09 c1[0] < c2[0];..
04b0: 09 7d 29 28 63 61 6e 64 29 3b 0a 09 09 63 20 3d .})(cand);...c =
04c0: 20 63 61 6e 64 5b 30 5d 5b 30 5d 3b 0a 0a 09 09 cand[0][0];....
04d0: 69 66 28 64 65 61 74 68 2e 63 6f 75 6e 74 28 63 if(death.count(c
04e0: 29 29 20 7b 0a 09 09 09 66 6f 72 65 61 63 68 28 )) {....foreach(
04f0: 63 68 61 72 20 6c 69 76 65 3b 20 22 55 44 4c 52 char live; "UDLR
0500: 57 41 22 29 0a 09 09 09 09 69 66 28 64 65 61 74 WA").....if(deat
0510: 68 2e 63 6f 75 6e 74 28 6c 69 76 65 29 3d 3d 30 h.count(live)==0
0520: 29 20 7b 0a 09 09 09 09 09 63 3d 6c 69 76 65 3b ) {......c=live;
0530: 0a 09 09 09 09 09 62 72 65 61 6b 3b 0a 09 09 09 ......break;....
0540: 09 7d 0a 09 09 7d 0a 0a 09 09 69 66 28 63 3d 3d .}...}....if(c==
0550: 27 57 27 29 20 7b 0a 09 09 09 77 61 69 74 5f 63 'W') {....wait_c
0560: 6f 75 6e 74 2b 2b 3b 0a 09 09 09 69 66 28 77 61 ount++;....if(wa
0570: 69 74 5f 63 6f 75 6e 74 20 3e 20 67 2e 6d 61 70 it_count > g.map
0580: 2e 48 29 0a 09 09 09 09 63 20 3d 20 27 41 27 3b .H).....c = 'A';
0590: 0a 09 09 7d 0a 09 09 65 6c 73 65 0a 09 09 09 77 ...}...else....w
05a0: 61 69 74 5f 63 6f 75 6e 74 20 3d 20 30 3b 0a 0a ait_count = 0;..
05b0: 09 09 62 6f 6f 6c 5b 63 68 61 72 5d 20 63 68 6f ..bool[char] cho
05c0: 69 63 65 3b 0a 09 09 66 6f 72 65 61 63 68 28 74 ice;...foreach(t
05d0: 3b 20 63 61 6e 64 29 0a 09 09 09 63 68 6f 69 63 ; cand)....choic
05e0: 65 5b 74 5b 30 5d 5d 20 3d 20 74 72 75 65 3b 0a e[t[0]] = true;.
05f0: 09 09 6c 6f 67 20 7e 3d 20 74 75 70 6c 65 28 72 ..log ~= tuple(r
0600: 6f 2e 63 6c 6f 6e 65 28 29 2c 20 63 61 73 74 28 o.clone(), cast(
0610: 69 6e 74 29 63 68 6f 69 63 65 2e 6c 65 6e 67 74 int)choice.lengt
0620: 68 29 3b 0a 09 09 69 66 28 6c 6f 67 2e 6c 65 6e h);...if(log.len
0630: 67 74 68 20 3e 20 35 29 0a 09 09 09 6c 6f 67 20 gth > 5)....log
0640: 3d 20 6c 6f 67 5b 24 2d 35 2e 2e 24 5d 3b 0a 09 = log[$-5..$];..
0650: 09 69 6e 74 20 63 6e 74 20 3d 20 30 3b 0a 09 09 .int cnt = 0;...
0660: 66 6f 72 65 61 63 68 28 6c 3b 20 6c 6f 67 29 0a foreach(l; log).
0670: 09 09 09 69 66 28 6c 5b 30 5d 20 3d 3d 20 6c 6f ...if(l[0] == lo
0680: 67 5b 24 2d 31 5d 5b 30 5d 29 0a 09 09 09 09 2b g[$-1][0]).....+
0690: 2b 63 6e 74 3b 0a 09 09 69 66 28 20 63 6e 74 20 +cnt;...if( cnt
06a0: 3e 3d 20 33 20 26 26 20 62 72 65 61 74 68 3d 3d >= 3 && breath==
06b0: 31 20 29 20 7b 0a 09 09 09 66 6f 72 62 69 64 64 1 ) {....forbidd
06c0: 65 6e 5f 63 65 6c 6c 5b 72 6f 2e 79 5d 5b 72 6f en_cell[ro.y][ro
06d0: 2e 78 5d 20 3d 20 74 72 75 65 3b 0a 09 09 7d 0a .x] = true;...}.
06e0: 0a 09 09 72 65 74 75 72 6e 20 63 3b 0a 09 7d 0a ...return c;..}.
06f0: 0a 09 54 75 70 6c 65 21 28 63 68 61 72 2c 69 6e ..Tuple!(char,in
0700: 74 29 5b 5d 20 73 65 61 72 63 68 28 69 6e 20 47 t)[] search(in G
0710: 61 6d 65 20 67 2c 20 69 6e 20 50 6f 73 20 73 2c ame g, in Pos s,
0720: 20 69 6e 20 50 6f 73 5b 5d 20 67 73 2c 20 73 74 in Pos[] gs, st
0730: 72 69 6e 67 20 64 65 61 74 68 29 0a 09 7b 0a 09 ring death)..{..
0740: 09 62 6f 6f 6c 20 64 61 6e 67 65 72 28 69 6e 74 .bool danger(int
0750: 20 79 2c 20 69 6e 74 20 78 29 0a 09 09 7b 0a 09 y, int x)...{..
0760: 09 09 69 66 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 ..if(g.map[y+1,x
0770: 5d 20 3d 3d 20 27 2a 27 29 0a 09 09 09 09 72 65 ] == '*').....re
0780: 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 turn true;....if
0790: 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 2d 31 5d 3d (g.map[y+1,x-1]=
07a0: 3d 27 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 ='*' && (g.map[y
07b0: 2c 78 2d 31 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d ,x-1]=='\\'||g.m
07c0: 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27 2a 27 29 20 ap[y,x-1]=='*')
07d0: 26 26 20 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d && (g.map[y+1,x]
07e0: 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2b 31 ==' '||g.map[y+1
07f0: 2c 78 5d 3d 3d 27 52 27 29 29 0a 09 09 09 09 72 ,x]=='R')).....r
0800: 65 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 eturn true;....i
0810: 66 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 2b 31 5d f(g.map[y+1,x+1]
0820: 3d 3d 27 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b =='*' && (g.map[
0830: 79 2c 78 2b 31 5d 3d 3d 27 2a 27 29 20 26 26 20 y,x+1]=='*') &&
0840: 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 (g.map[y+1,x]=='
0850: 20 27 7c 7c 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d '||g.map[y+1,x]
0860: 3d 3d 27 52 27 29 29 0a 09 09 09 09 72 65 74 75 =='R')).....retu
0870: 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 28 67 rn true;....if(g
0880: 2e 6d 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27 2a 27 .map[y,x-1]=='*'
0890: 20 26 26 20 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 && (g.map[y-1,x
08a0: 2d 31 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 -1]=='\\'||g.map
08b0: 5b 79 2d 31 2c 78 2d 31 5d 3d 3d 27 2a 27 29 20 [y-1,x-1]=='*')
08c0: 26 26 20 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d && (g.map[y-1,x]
08d0: 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2d 31 ==' '||g.map[y-1
08e0: 2c 78 5d 3d 3d 27 52 27 29 29 0a 09 09 09 09 72 ,x]=='R')).....r
08f0: 65 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 eturn true;....i
0900: 66 28 67 2e 6d 61 70 5b 79 2c 78 2b 31 5d 3d 3d f(g.map[y,x+1]==
0910: 27 2a 27 20 26 26 20 28 67 2e 6d 61 70 5b 79 2d '*' && (g.map[y-
0920: 31 2c 78 2b 31 5d 3d 3d 27 2a 27 29 20 26 26 20 1,x+1]=='*') &&
0930: 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 (g.map[y-1,x]=='
0940: 20 27 7c 7c 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d '||g.map[y-1,x]
0950: 3d 3d 27 52 27 29 29 0a 09 09 09 09 72 65 74 75 =='R')).....retu
0960: 72 6e 20 74 72 75 65 3b 0a 09 09 09 72 65 74 75 rn true;....retu
0970: 72 6e 20 66 61 6c 73 65 3b 0a 09 09 7d 0a 0a 09 rn false;...}...
0980: 09 2f 2f 20 61 76 6f 69 64 20 64 69 72 65 63 74 .// avoid direct
0990: 6c 79 20 62 65 6c 6f 77 20 27 2a 27 0a 09 09 54 ly below '*'...T
09a0: 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b uple!(char,int)[
09b0: 5d 20 74 72 79 41 28 29 20 7b 0a 09 09 09 63 6f ] tryA() {....co
09c0: 6e 73 74 28 50 6f 73 29 5b 5d 20 71 3b 0a 09 09 nst(Pos)[] q;...
09d0: 09 66 6f 72 65 61 63 68 28 70 3b 20 67 73 29 0a .foreach(p; gs).
09e0: 09 09 09 09 69 66 28 21 64 61 6e 67 65 72 28 70 ....if(!danger(p
09f0: 2e 79 2c 70 2e 78 29 29 0a 09 09 09 09 09 71 20 .y,p.x))......q
0a00: 7e 3d 20 70 3b 0a 09 09 09 62 6f 6f 6c 5b 5d 5b ~= p;....bool[][
0a10: 5d 20 76 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d ] v = new bool[]
0a20: 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e [](g.map.H+2, g.
0a30: 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 09 66 6f 72 map.W+2);....for
0a40: 65 61 63 68 28 70 3b 20 71 29 20 76 5b 70 2e 79 each(p; q) v[p.y
0a50: 5d 5b 70 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 09 ][p.x]=true;....
0a60: 66 6f 72 28 69 6e 74 20 73 74 65 70 3d 31 3b 20 for(int step=1;
0a70: 71 2e 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 q.length; ++step
0a80: 29 20 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 71 32 ) {.....Pos[] q2
0a90: 3b 0a 09 09 09 09 66 6f 72 65 61 63 68 28 70 3b ;.....foreach(p;
0aa0: 20 71 29 20 7b 0a 09 09 09 09 09 69 6e 74 5b 5d q) {......int[]
0ab0: 20 64 79 3d 5b 2d 31 2c 2b 31 2c 30 2c 30 5d 3b dy=[-1,+1,0,0];
0ac0: 0a 09 09 09 09 09 69 6e 74 5b 5d 20 64 78 3d 5b ......int[] dx=[
0ad0: 30 2c 30 2c 2d 31 2c 2b 31 5d 3b 0a 09 09 09 09 0,0,-1,+1];.....
0ae0: 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c .for(int i=0; i<
0af0: 34 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 09 4; ++i) {.......
0b00: 69 6e 74 20 79 20 3d 20 70 2e 79 2b 64 79 5b 69 int y = p.y+dy[i
0b10: 5d 3b 0a 09 09 09 09 09 09 69 6e 74 20 78 20 3d ];.......int x =
0b20: 20 70 2e 78 2b 64 78 5b 69 5d 3b 0a 09 09 09 09 p.x+dx[i];.....
0b30: 09 09 69 66 28 76 5b 79 5d 5b 78 5d 29 20 63 6f ..if(v[y][x]) co
0b40: 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 69 66 ntinue;.......if
0b50: 28 79 3d 3d 73 2e 79 20 26 26 20 78 3d 3d 73 2e (y==s.y && x==s.
0b60: 78 29 20 7b 0a 09 09 09 09 09 09 09 63 68 61 72 x) {........char
0b70: 20 63 20 3d 20 22 55 44 52 4c 22 5b 69 5d 3b 0a c = "UDRL"[i];.
0b80: 09 09 09 09 09 09 09 69 66 28 20 64 65 61 74 68 .......if( death
0b90: 2e 63 6f 75 6e 74 28 63 29 20 3d 3d 20 30 20 29 .count(c) == 0 )
0ba0: 0a 09 09 09 09 09 09 09 09 72 65 74 75 72 6e 20 .........return
0bb0: 5b 74 75 70 6c 65 28 63 2c 73 74 65 70 29 5d 3b [tuple(c,step)];
0bc0: 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 .......} else if
0bd0: 28 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 5b (forbidden_cell[
0be0: 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 09 09 7d 20 y][x]){.......}
0bf0: 65 6c 73 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c else if(g.map[y,
0c00: 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 x]==' '||g.map[y
0c10: 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 ,x]=='\\'||g.map
0c20: 5b 79 2c 78 5d 3d 3d 27 2e 27 29 20 7b 0a 09 09 [y,x]=='.') {...
0c30: 09 09 09 09 09 69 66 28 64 61 6e 67 65 72 28 79 .....if(danger(y
0c40: 2c 78 29 29 0a 09 09 09 09 09 09 09 09 63 6f 6e ,x)).........con
0c50: 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 09 71 32 tinue;........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 76 5b 79 5d 5b 78 5d ;........v[y][x]
0c80: 3d 74 72 75 65 3b 0a 09 09 09 09 09 09 7d 0a 09 =true;.......}..
0c90: 09 09 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 09 ....}.....}.....
0ca0: 71 20 3d 20 71 32 3b 0a 09 09 09 7d 0a 09 09 09 q = q2;....}....
0cb0: 72 65 74 75 72 6e 20 5b 5d 3b 0a 09 09 7d 0a 0a return [];...}..
0cc0: 09 09 2f 2f 20 61 6e 79 20 65 6d 70 74 79 20 73 ..// any empty s
0cd0: 70 61 63 65 20 69 73 20 6d 79 20 67 72 6f 75 6e pace is my groun
0ce0: 64 0a 09 09 54 75 70 6c 65 21 28 63 68 61 72 2c d...Tuple!(char,
0cf0: 69 6e 74 29 5b 5d 20 74 72 79 42 28 29 20 7b 0a int)[] tryB() {.
0d00: 09 09 09 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 ...const(Pos)[]
0d10: 71 3b 0a 09 09 09 66 6f 72 65 61 63 68 28 70 3b q;....foreach(p;
0d20: 20 67 73 29 20 71 20 7e 3d 20 70 3b 0a 09 09 09 gs) q ~= p;....
0d30: 62 6f 6f 6c 5b 5d 5b 5d 20 76 20 3d 20 6e 65 77 bool[][] v = new
0d40: 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 70 2e bool[][](g.map.
0d50: 48 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 29 3b H+2, g.map.W+2);
0d60: 0a 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 ....foreach(p; q
0d70: 29 20 76 5b 70 2e 79 5d 5b 70 2e 78 5d 3d 74 72 ) v[p.y][p.x]=tr
0d80: 75 65 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 73 ue;....for(int s
0d90: 74 65 70 3d 31 30 3b 20 71 2e 6c 65 6e 67 74 68 tep=10; q.length
0da0: 3b 20 2b 2b 73 74 65 70 29 20 7b 0a 09 09 09 09 ; ++step) {.....
0db0: 50 6f 73 5b 5d 20 71 32 3b 0a 09 09 09 09 66 6f Pos[] q2;.....fo
0dc0: 72 65 61 63 68 28 70 3b 20 71 29 20 7b 0a 09 09 reach(p; q) {...
0dd0: 09 09 09 69 6e 74 5b 5d 20 64 79 3d 5b 2d 31 2c ...int[] dy=[-1,
0de0: 2b 31 2c 30 2c 30 5d 3b 0a 09 09 09 09 09 69 6e +1,0,0];......in
0df0: 74 5b 5d 20 64 78 3d 5b 30 2c 30 2c 2d 31 2c 2b t[] dx=[0,0,-1,+
0e00: 31 5d 3b 0a 09 09 09 09 09 66 6f 72 28 69 6e 74 1];......for(int
0e10: 20 69 3d 30 3b 20 69 3c 34 3b 20 2b 2b 69 29 20 i=0; i<4; ++i)
0e20: 7b 0a 09 09 09 09 09 09 69 6e 74 20 79 20 3d 20 {.......int y =
0e30: 70 2e 79 2b 64 79 5b 69 5d 3b 0a 09 09 09 09 09 p.y+dy[i];......
0e40: 09 69 6e 74 20 78 20 3d 20 70 2e 78 2b 64 78 5b .int x = p.x+dx[
0e50: 69 5d 3b 0a 09 09 09 09 09 09 69 66 28 76 5b 79 i];.......if(v[y
0e60: 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a ][x]) continue;.
0e70: 09 09 09 09 09 09 69 66 28 79 3d 3d 73 2e 79 20 ......if(y==s.y
0e80: 26 26 20 78 3d 3d 73 2e 78 29 20 7b 0a 09 09 09 && x==s.x) {....
0e90: 09 09 09 09 63 68 61 72 20 63 20 3d 20 22 55 44 ....char c = "UD
0ea0: 52 4c 22 5b 69 5d 3b 0a 09 09 09 09 09 09 09 69 RL"[i];........i
0eb0: 66 28 20 64 65 61 74 68 2e 63 6f 75 6e 74 28 63 f( death.count(c
0ec0: 29 20 3d 3d 20 30 20 29 0a 09 09 09 09 09 09 09 ) == 0 )........
0ed0: 09 72 65 74 75 72 6e 20 5b 74 75 70 6c 65 28 63 .return [tuple(c
0ee0: 2c 73 74 65 70 29 5d 3b 0a 09 09 09 09 09 09 7d ,step)];.......}
0ef0: 20 65 6c 73 65 20 69 66 28 66 6f 72 62 69 64 64 else if(forbidd
0f00: 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 5d 29 7b 0a en_cell[y][x]){.
0f10: 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 ......} else if(
0f20: 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c g.map[y,x]==' '|
0f30: 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c |g.map[y,x]=='\\
0f40: 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 '||g.map[y,x]=='
0f50: 2e 27 29 20 7b 0a 09 09 09 09 09 09 09 71 32 20 .') {........q2
0f60: 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b ~= new Pos(y,x);
0f70: 0a 09 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d 3d ........v[y][x]=
0f80: 74 72 75 65 3b 0a 09 09 09 09 09 09 7d 0a 09 09 true;.......}...
0f90: 09 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 09 71 ...}.....}.....q
0fa0: 20 3d 20 71 32 3b 0a 09 09 09 7d 0a 09 09 09 72 = q2;....}....r
0fb0: 65 74 75 72 6e 20 5b 5d 3b 0a 09 09 7d 0a 0a 09 eturn [];...}...
0fc0: 09 2f 2f 20 70 75 73 68 20 72 6f 63 6b 73 21 0a .// push rocks!.
0fd0: 09 09 54 75 70 6c 65 21 28 63 68 61 72 2c 69 6e ..Tuple!(char,in
0fe0: 74 29 5b 5d 20 74 72 79 43 28 29 20 7b 0a 09 09 t)[] tryC() {...
0ff0: 09 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 71 3b .const(Pos)[] q;
1000: 0a 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 67 ....foreach(p; g
1010: 73 29 20 71 20 7e 3d 20 70 3b 0a 09 09 09 62 6f s) q ~= p;....bo
1020: 6f 6c 5b 5d 5b 5d 20 76 20 3d 20 6e 65 77 20 62 ol[][] v = new b
1030: 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b ool[][](g.map.H+
1040: 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 2, g.map.W+2);..
1050: 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 ..foreach(p; q)
1060: 76 5b 70 2e 79 5d 5b 70 2e 78 5d 3d 74 72 75 65 v[p.y][p.x]=true
1070: 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 73 74 65 ;....for(int ste
1080: 70 3d 32 30 3b 20 71 2e 6c 65 6e 67 74 68 3b 20 p=20; q.length;
1090: 2b 2b 73 74 65 70 29 20 7b 0a 09 09 09 09 50 6f ++step) {.....Po
10a0: 73 5b 5d 20 71 32 3b 0a 09 09 09 09 66 6f 72 65 s[] q2;.....fore
10b0: 61 63 68 28 70 3b 20 71 29 20 7b 0a 09 09 09 09 ach(p; q) {.....
10c0: 09 69 6e 74 5b 5d 20 64 79 3d 5b 2d 31 2c 2b 31 .int[] dy=[-1,+1
10d0: 2c 30 2c 30 5d 3b 0a 09 09 09 09 09 69 6e 74 5b ,0,0];......int[
10e0: 5d 20 64 78 3d 5b 30 2c 30 2c 2d 31 2c 2b 31 5d ] dx=[0,0,-1,+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 34 3b 20 2b 2b 69 29 20 7b 0a =0; i<4; ++i) {.
1110: 09 09 09 09 09 09 69 6e 74 20 79 20 3d 20 70 2e ......int y = p.
1120: 79 2b 64 79 5b 69 5d 3b 0a 09 09 09 09 09 09 69 y+dy[i];.......i
1130: 6e 74 20 78 20 3d 20 70 2e 78 2b 64 78 5b 69 5d nt x = p.x+dx[i]
1140: 3b 0a 09 09 09 09 09 09 69 66 28 76 5b 79 5d 5b ;.......if(v[y][
1150: 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 x]) continue;...
1160: 09 09 09 09 69 66 28 79 3d 3d 73 2e 79 20 26 26 ....if(y==s.y &&
1170: 20 78 3d 3d 73 2e 78 29 20 7b 0a 09 09 09 09 09 x==s.x) {......
1180: 09 09 63 68 61 72 20 63 20 3d 20 22 55 44 52 4c ..char c = "UDRL
1190: 22 5b 69 5d 3b 0a 09 09 09 09 09 09 09 69 66 28 "[i];........if(
11a0: 20 64 65 61 74 68 2e 63 6f 75 6e 74 28 63 29 20 death.count(c)
11b0: 3d 3d 20 30 20 29 0a 09 09 09 09 09 09 09 09 72 == 0 ).........r
11c0: 65 74 75 72 6e 20 5b 74 75 70 6c 65 28 63 2c 73 eturn [tuple(c,s
11d0: 74 65 70 29 5d 3b 0a 09 09 09 09 09 09 7d 20 65 tep)];.......} e
11e0: 6c 73 65 20 69 66 28 66 6f 72 62 69 64 64 65 6e lse if(forbidden
11f0: 5f 63 65 6c 6c 5b 79 5d 5b 78 5d 29 7b 0a 09 09 _cell[y][x]){...
1200: 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 67 2e ....} else if(g.
1210: 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c 7c 67 map[y,x]==' '||g
1220: 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c 27 7c .map[y,x]=='\\'|
1230: 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 |g.map[y,x]=='.'
1240: 29 20 7b 0a 09 09 09 09 09 09 09 71 32 20 7e 3d ) {........q2 ~=
1250: 20 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 new Pos(y,x);..
1260: 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 ......v[y][x]=tr
1270: 75 65 3b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 ue;.......} else
1280: 20 69 66 28 64 79 5b 69 5d 3d 3d 30 20 26 26 20 if(dy[i]==0 &&
1290: 67 2e 6d 61 70 5b 70 5d 3d 3d 27 20 27 20 26 26 g.map[p]==' ' &&
12a0: 20 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2a 27 g.map[y,x]=='*'
12b0: 20 26 26 20 28 67 2e 6d 61 70 5b 79 2b 64 79 5b && (g.map[y+dy[
12c0: 69 5d 2c 78 2b 64 78 5b 69 5d 5d 3d 3d 27 20 27 i],x+dx[i]]==' '
12d0: 7c 7c 67 2e 6d 61 70 5b 79 2b 64 79 5b 69 5d 2c ||g.map[y+dy[i],
12e0: 78 2b 64 78 5b 69 5d 5d 3d 3d 27 52 27 29 29 20 x+dx[i]]=='R'))
12f0: 7b 0a 09 09 09 09 09 09 09 71 32 20 7e 3d 20 6e {........q2 ~= n
1300: 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 ew Pos(y,x);....
1310: 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 ....v[y][x]=true
1320: 3b 0a 09 09 09 09 09 09 7d 0a 09 09 09 09 09 7d ;.......}......}
1330: 0a 09 09 09 09 7d 0a 09 09 09 09 71 20 3d 20 71 .....}.....q = q
1340: 32 3b 0a 09 09 09 7d 0a 09 09 09 72 65 74 75 72 2;....}....retur
1350: 6e 20 5b 5d 3b 0a 09 09 7d 0a 09 09 72 65 74 75 n [];...}...retu
1360: 72 6e 20 74 72 79 41 28 29 20 7e 20 74 72 79 42 rn tryA() ~ tryB
1370: 28 29 20 7e 20 74 72 79 43 28 29 3b 0a 09 7d 0a () ~ tryC();..}.
1380: 7d 0a }.