Hex Artifact Content
Not logged in

Artifact 69c19d5fe197eaada0516767df0713e43285f920:


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 2c 20 74 72 75 65 29 3b 0a 09   death, true);..
0550: 09 7d 0a 0a 09 09 69 66 28 63 61 6e 64 2e 65 6d  .}....if(cand.em
0560: 70 74 79 29 0a 09 09 09 63 61 6e 64 20 7e 3d 20  pty)....cand ~= 
0570: 74 75 70 6c 65 28 27 57 27 2c 69 6e 74 2e 6d 61  tuple('W',int.ma
0580: 78 29 3b 0a 09 09 73 6f 72 74 21 28 28 54 75 70  x);...sort!((Tup
0590: 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 20 63 31  le!(char,int) c1
05a0: 2c 20 54 75 70 6c 65 21 28 63 68 61 72 2c 69 6e  , Tuple!(char,in
05b0: 74 29 20 63 32 29 7b 0a 09 09 09 69 66 28 63 31  t) c2){....if(c1
05c0: 5b 31 5d 20 21 3d 20 63 32 5b 31 5d 29 0a 09 09  [1] != c2[1])...
05d0: 09 09 72 65 74 75 72 6e 20 63 31 5b 31 5d 20 3c  ..return c1[1] <
05e0: 20 63 32 5b 31 5d 3b 0a 09 09 09 72 65 74 75 72   c2[1];....retur
05f0: 6e 20 63 31 5b 30 5d 20 3c 20 63 32 5b 30 5d 3b  n c1[0] < c2[0];
0600: 0a 09 09 7d 29 28 63 61 6e 64 29 3b 0a 09 09 63  ...})(cand);...c
0610: 20 3d 20 63 61 6e 64 5b 30 5d 5b 30 5d 3b 0a 0a   = cand[0][0];..
0620: 09 09 69 66 28 64 65 61 74 68 2e 63 6f 75 6e 74  ..if(death.count
0630: 28 63 29 29 20 7b 0a 09 09 09 66 6f 72 65 61 63  (c)) {....foreac
0640: 68 28 63 68 61 72 20 6c 69 76 65 3b 20 22 55 44  h(char live; "UD
0650: 4c 52 57 41 22 29 0a 09 09 09 09 69 66 28 64 65  LRWA").....if(de
0660: 61 74 68 2e 63 6f 75 6e 74 28 6c 69 76 65 29 3d  ath.count(live)=
0670: 3d 30 29 20 7b 0a 09 09 09 09 09 63 3d 6c 69 76  =0) {......c=liv
0680: 65 3b 0a 09 09 09 09 09 62 72 65 61 6b 3b 0a 09  e;......break;..
0690: 09 09 09 7d 0a 09 09 7d 0a 0a 09 09 69 66 28 63  ...}...}....if(c
06a0: 3d 3d 27 57 27 29 20 7b 0a 09 09 09 77 61 69 74  =='W') {....wait
06b0: 5f 63 6f 75 6e 74 2b 2b 3b 0a 09 09 09 69 66 28  _count++;....if(
06c0: 77 61 69 74 5f 63 6f 75 6e 74 20 3e 20 67 2e 6d  wait_count > g.m
06d0: 61 70 2e 48 29 0a 09 09 09 09 63 20 3d 20 27 41  ap.H).....c = 'A
06e0: 27 3b 0a 09 09 7d 0a 09 09 65 6c 73 65 0a 09 09  ';...}...else...
06f0: 09 77 61 69 74 5f 63 6f 75 6e 74 20 3d 20 30 3b  .wait_count = 0;
0700: 0a 0a 09 09 62 6f 6f 6c 5b 63 68 61 72 5d 20 63  ....bool[char] c
0710: 68 6f 69 63 65 3b 0a 09 09 66 6f 72 65 61 63 68  hoice;...foreach
0720: 28 74 3b 20 63 61 6e 64 29 0a 09 09 09 63 68 6f  (t; cand)....cho
0730: 69 63 65 5b 74 5b 30 5d 5d 20 3d 20 74 72 75 65  ice[t[0]] = true
0740: 3b 0a 09 09 6c 6f 67 20 7e 3d 20 74 75 70 6c 65  ;...log ~= tuple
0750: 28 72 6f 2e 63 6c 6f 6e 65 28 29 2c 20 63 61 73  (ro.clone(), cas
0760: 74 28 69 6e 74 29 63 68 6f 69 63 65 2e 6c 65 6e  t(int)choice.len
0770: 67 74 68 29 3b 0a 09 09 69 66 28 6c 6f 67 2e 6c  gth);...if(log.l
0780: 65 6e 67 74 68 20 3e 20 35 29 0a 09 09 09 6c 6f  ength > 5)....lo
0790: 67 20 3d 20 6c 6f 67 5b 24 2d 35 2e 2e 24 5d 3b  g = log[$-5..$];
07a0: 0a 09 09 69 6e 74 20 63 6e 74 20 3d 20 30 3b 0a  ...int cnt = 0;.
07b0: 09 09 66 6f 72 65 61 63 68 28 6c 3b 20 6c 6f 67  ..foreach(l; log
07c0: 29 0a 09 09 09 69 66 28 6c 5b 30 5d 20 3d 3d 20  )....if(l[0] == 
07d0: 6c 6f 67 5b 24 2d 31 5d 5b 30 5d 29 0a 09 09 09  log[$-1][0])....
07e0: 09 2b 2b 63 6e 74 3b 0a 09 09 69 66 28 20 63 6e  .++cnt;...if( cn
07f0: 74 20 3e 3d 20 33 20 26 26 20 62 72 65 61 74 68  t >= 3 && breath
0800: 3d 3d 31 20 29 20 7b 0a 09 09 09 66 6f 72 62 69  ==1 ) {....forbi
0810: 64 64 65 6e 5f 63 65 6c 6c 5b 72 6f 2e 79 5d 5b  dden_cell[ro.y][
0820: 72 6f 2e 78 5d 20 3d 20 74 72 75 65 3b 0a 09 09  ro.x] = true;...
0830: 7d 0a 0a 09 09 72 65 74 75 72 6e 20 63 3b 0a 09  }....return c;..
0840: 7d 0a 0a 09 54 75 70 6c 65 21 28 63 68 61 72 2c  }...Tuple!(char,
0850: 69 6e 74 29 5b 5d 20 73 65 61 72 63 68 28 69 6e  int)[] search(in
0860: 20 47 61 6d 65 20 67 2c 20 69 6e 20 50 6f 73 20   Game g, in Pos 
0870: 73 2c 20 69 6e 20 50 6f 73 5b 5d 20 67 73 2c 20  s, in Pos[] gs, 
0880: 73 74 72 69 6e 67 20 64 65 61 74 68 2c 20 62 6f  string death, bo
0890: 6f 6c 20 64 61 6e 67 65 72 5f 6f 6b 3d 66 61 6c  ol danger_ok=fal
08a0: 73 65 29 0a 09 7b 0a 09 09 62 6f 6f 6c 20 64 61  se)..{...bool da
08b0: 6e 67 65 72 28 69 6e 74 20 79 2c 20 69 6e 74 20  nger(int y, int 
08c0: 78 29 0a 09 09 7b 0a 09 09 09 69 66 28 67 2e 6d  x)...{....if(g.m
08d0: 61 70 5b 79 2c 78 5d 20 3d 3d 20 27 20 27 20 7c  ap[y,x] == ' ' |
08e0: 7c 20 67 2e 6d 61 70 5b 79 2c 78 5d 20 3d 3d 20  | g.map[y,x] == 
08f0: 27 52 27 29 0a 09 09 09 09 72 65 74 75 72 6e 20  'R').....return 
0900: 66 61 6c 73 65 3b 0a 09 09 09 69 66 28 67 2e 6d  false;....if(g.m
0910: 61 70 5b 79 2b 31 2c 78 5d 20 3d 3d 20 27 2a 27  ap[y+1,x] == '*'
0920: 29 0a 09 09 09 09 72 65 74 75 72 6e 20 74 72 75  ).....return tru
0930: 65 3b 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b 79  e;....if(g.map[y
0940: 2b 31 2c 78 2d 31 5d 3d 3d 27 2a 27 20 26 26 20  +1,x-1]=='*' && 
0950: 28 67 2e 6d 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27  (g.map[y,x-1]=='
0960: 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 2d 31  \\'||g.map[y,x-1
0970: 5d 3d 3d 27 2a 27 29 20 26 26 20 28 67 2e 6d 61  ]=='*') && (g.ma
0980: 70 5b 79 2b 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67  p[y+1,x]==' '||g
0990: 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d 3d 27 52 27  .map[y+1,x]=='R'
09a0: 29 29 0a 09 09 09 09 72 65 74 75 72 6e 20 74 72  )).....return tr
09b0: 75 65 3b 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b  ue;....if(g.map[
09c0: 79 2b 31 2c 78 2b 31 5d 3d 3d 27 2a 27 20 26 26  y+1,x+1]=='*' &&
09d0: 20 28 67 2e 6d 61 70 5b 79 2c 78 2b 31 5d 3d 3d   (g.map[y,x+1]==
09e0: 27 2a 27 29 20 26 26 20 28 67 2e 6d 61 70 5b 79  '*') && (g.map[y
09f0: 2b 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61  +1,x]==' '||g.ma
0a00: 70 5b 79 2b 31 2c 78 5d 3d 3d 27 52 27 29 29 0a  p[y+1,x]=='R')).
0a10: 09 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b  ....return true;
0a20: 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2c 78  ....if(g.map[y,x
0a30: 2d 31 5d 3d 3d 27 2a 27 20 26 26 20 28 67 2e 6d  -1]=='*' && (g.m
0a40: 61 70 5b 79 2d 31 2c 78 2d 31 5d 3d 3d 27 5c 5c  ap[y-1,x-1]=='\\
0a50: 27 7c 7c 67 2e 6d 61 70 5b 79 2d 31 2c 78 2d 31  '||g.map[y-1,x-1
0a60: 5d 3d 3d 27 2a 27 29 20 26 26 20 28 67 2e 6d 61  ]=='*') && (g.ma
0a70: 70 5b 79 2d 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67  p[y-1,x]==' '||g
0a80: 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 52 27  .map[y-1,x]=='R'
0a90: 29 29 0a 09 09 09 09 72 65 74 75 72 6e 20 74 72  )).....return tr
0aa0: 75 65 3b 0a 09 09 09 69 66 28 67 2e 6d 61 70 5b  ue;....if(g.map[
0ab0: 79 2c 78 2b 31 5d 3d 3d 27 2a 27 20 26 26 20 28  y,x+1]=='*' && (
0ac0: 67 2e 6d 61 70 5b 79 2d 31 2c 78 2b 31 5d 3d 3d  g.map[y-1,x+1]==
0ad0: 27 2a 27 29 20 26 26 20 28 67 2e 6d 61 70 5b 79  '*') && (g.map[y
0ae0: 2d 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61  -1,x]==' '||g.ma
0af0: 70 5b 79 2d 31 2c 78 5d 3d 3d 27 52 27 29 29 0a  p[y-1,x]=='R')).
0b00: 09 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b  ....return true;
0b10: 0a 09 09 09 72 65 74 75 72 6e 20 66 61 6c 73 65  ....return false
0b20: 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 61 76 6f 69  ;...}....// avoi
0b30: 64 20 64 69 72 65 63 74 6c 79 20 62 65 6c 6f 77  d directly below
0b40: 20 27 2a 27 0a 09 09 54 75 70 6c 65 21 28 63 68   '*'...Tuple!(ch
0b50: 61 72 2c 69 6e 74 29 5b 5d 20 74 72 79 41 28 29  ar,int)[] tryA()
0b60: 20 7b 0a 09 09 09 63 6f 6e 73 74 28 50 6f 73 29   {....const(Pos)
0b70: 5b 5d 20 71 3b 0a 09 09 09 66 6f 72 65 61 63 68  [] q;....foreach
0b80: 28 70 3b 20 67 73 29 0a 09 09 09 09 69 66 28 21  (p; gs).....if(!
0b90: 64 61 6e 67 65 72 28 70 2e 79 2c 70 2e 78 29 29  danger(p.y,p.x))
0ba0: 0a 09 09 09 09 09 71 20 7e 3d 20 70 3b 0a 09 09  ......q ~= p;...
0bb0: 09 62 6f 6f 6c 5b 5d 5b 5d 20 76 20 3d 20 6e 65  .bool[][] v = ne
0bc0: 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61 70  w bool[][](g.map
0bd0: 2e 48 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 29  .H+2, g.map.W+2)
0be0: 3b 0a 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20  ;....foreach(p; 
0bf0: 71 29 20 76 5b 70 2e 79 5d 5b 70 2e 78 5d 3d 74  q) v[p.y][p.x]=t
0c00: 72 75 65 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20  rue;....for(int 
0c10: 73 74 65 70 3d 31 3b 20 71 2e 6c 65 6e 67 74 68  step=1; q.length
0c20: 3b 20 2b 2b 73 74 65 70 29 20 7b 0a 09 09 09 09  ; ++step) {.....
0c30: 50 6f 73 5b 5d 20 71 32 3b 0a 09 09 09 09 66 6f  Pos[] q2;.....fo
0c40: 72 65 61 63 68 28 70 3b 20 71 29 20 7b 0a 09 09  reach(p; q) {...
0c50: 09 09 09 69 6e 74 5b 5d 20 64 79 3d 5b 2d 31 2c  ...int[] dy=[-1,
0c60: 2b 31 2c 30 2c 30 5d 3b 0a 09 09 09 09 09 69 6e  +1,0,0];......in
0c70: 74 5b 5d 20 64 78 3d 5b 30 2c 30 2c 2d 31 2c 2b  t[] dx=[0,0,-1,+
0c80: 31 5d 3b 0a 09 09 09 09 09 66 6f 72 28 69 6e 74  1];......for(int
0c90: 20 69 3d 30 3b 20 69 3c 34 3b 20 2b 2b 69 29 20   i=0; i<4; ++i) 
0ca0: 7b 0a 09 09 09 09 09 09 69 6e 74 20 79 20 3d 20  {.......int y = 
0cb0: 70 2e 79 2b 64 79 5b 69 5d 3b 0a 09 09 09 09 09  p.y+dy[i];......
0cc0: 09 69 6e 74 20 78 20 3d 20 70 2e 78 2b 64 78 5b  .int x = p.x+dx[
0cd0: 69 5d 3b 0a 09 09 09 09 09 09 69 66 28 76 5b 79  i];.......if(v[y
0ce0: 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a  ][x]) continue;.
0cf0: 09 09 09 09 09 09 69 66 28 79 3d 3d 73 2e 79 20  ......if(y==s.y 
0d00: 26 26 20 78 3d 3d 73 2e 78 29 20 7b 0a 09 09 09  && x==s.x) {....
0d10: 09 09 09 09 63 68 61 72 20 63 20 3d 20 22 55 44  ....char c = "UD
0d20: 52 4c 22 5b 69 5d 3b 0a 09 09 09 09 09 09 09 69  RL"[i];........i
0d30: 66 28 20 64 65 61 74 68 2e 63 6f 75 6e 74 28 63  f( death.count(c
0d40: 29 20 3d 3d 20 30 20 29 0a 09 09 09 09 09 09 09  ) == 0 )........
0d50: 09 72 65 74 75 72 6e 20 5b 74 75 70 6c 65 28 63  .return [tuple(c
0d60: 2c 73 74 65 70 29 5d 3b 0a 09 09 09 09 09 09 7d  ,step)];.......}
0d70: 20 65 6c 73 65 20 69 66 28 66 6f 72 62 69 64 64   else if(forbidd
0d80: 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 5d 29 7b 0a  en_cell[y][x]){.
0d90: 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28  ......} else if(
0da0: 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c  g.map[y,x]==' '|
0db0: 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c  |g.map[y,x]=='\\
0dc0: 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27  '||g.map[y,x]=='
0dd0: 2e 27 29 20 7b 0a 09 09 09 09 09 09 09 69 66 28  .') {........if(
0de0: 64 61 6e 67 65 72 28 79 2c 78 29 29 0a 09 09 09  danger(y,x))....
0df0: 09 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0a 09  .....continue;..
0e00: 09 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20  ......q2 ~= new 
0e10: 50 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09  Pos(y,x);.......
0e20: 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09  .v[y][x]=true;..
0e30: 09 09 09 09 09 7d 0a 09 09 09 09 09 7d 0a 09 09  .....}......}...
0e40: 09 09 7d 0a 09 09 09 09 71 20 3d 20 71 32 3b 0a  ..}.....q = q2;.
0e50: 09 09 09 7d 0a 09 09 09 72 65 74 75 72 6e 20 5b  ...}....return [
0e60: 5d 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 61 6e 79  ];...}....// any
0e70: 20 65 6d 70 74 79 20 73 70 61 63 65 20 69 73 20   empty space is 
0e80: 6d 79 20 67 72 6f 75 6e 64 0a 09 09 54 75 70 6c  my ground...Tupl
0e90: 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d 20 74  e!(char,int)[] t
0ea0: 72 79 42 28 29 20 7b 0a 09 09 09 63 6f 6e 73 74  ryB() {....const
0eb0: 28 50 6f 73 29 5b 5d 20 71 3b 0a 09 09 09 66 6f  (Pos)[] q;....fo
0ec0: 72 65 61 63 68 28 70 3b 20 67 73 29 20 71 20 7e  reach(p; gs) q ~
0ed0: 3d 20 70 3b 0a 09 09 09 62 6f 6f 6c 5b 5d 5b 5d  = p;....bool[][]
0ee0: 20 76 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b   v = new bool[][
0ef0: 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d  ](g.map.H+2, g.m
0f00: 61 70 2e 57 2b 32 29 3b 0a 09 09 09 66 6f 72 65  ap.W+2);....fore
0f10: 61 63 68 28 70 3b 20 71 29 20 76 5b 70 2e 79 5d  ach(p; q) v[p.y]
0f20: 5b 70 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 09 66  [p.x]=true;....f
0f30: 6f 72 28 69 6e 74 20 73 74 65 70 3d 31 30 3b 20  or(int step=10; 
0f40: 71 2e 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70  q.length; ++step
0f50: 29 20 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 71 32  ) {.....Pos[] q2
0f60: 3b 0a 09 09 09 09 66 6f 72 65 61 63 68 28 70 3b  ;.....foreach(p;
0f70: 20 71 29 20 7b 0a 09 09 09 09 09 69 6e 74 5b 5d   q) {......int[]
0f80: 20 64 79 3d 5b 2d 31 2c 2b 31 2c 30 2c 30 5d 3b   dy=[-1,+1,0,0];
0f90: 0a 09 09 09 09 09 69 6e 74 5b 5d 20 64 78 3d 5b  ......int[] dx=[
0fa0: 30 2c 30 2c 2d 31 2c 2b 31 5d 3b 0a 09 09 09 09  0,0,-1,+1];.....
0fb0: 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c  .for(int i=0; i<
0fc0: 34 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 09  4; ++i) {.......
0fd0: 69 6e 74 20 79 20 3d 20 70 2e 79 2b 64 79 5b 69  int y = p.y+dy[i
0fe0: 5d 3b 0a 09 09 09 09 09 09 69 6e 74 20 78 20 3d  ];.......int x =
0ff0: 20 70 2e 78 2b 64 78 5b 69 5d 3b 0a 09 09 09 09   p.x+dx[i];.....
1000: 09 09 69 66 28 76 5b 79 5d 5b 78 5d 29 20 63 6f  ..if(v[y][x]) co
1010: 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 69 66  ntinue;.......if
1020: 28 79 3d 3d 73 2e 79 20 26 26 20 78 3d 3d 73 2e  (y==s.y && x==s.
1030: 78 29 20 7b 0a 09 09 09 09 09 09 09 63 68 61 72  x) {........char
1040: 20 63 20 3d 20 22 55 44 52 4c 22 5b 69 5d 3b 0a   c = "UDRL"[i];.
1050: 09 09 09 09 09 09 09 69 66 28 20 64 65 61 74 68  .......if( death
1060: 2e 63 6f 75 6e 74 28 63 29 20 3d 3d 20 30 20 29  .count(c) == 0 )
1070: 0a 09 09 09 09 09 09 09 09 72 65 74 75 72 6e 20  .........return 
1080: 5b 74 75 70 6c 65 28 63 2c 73 74 65 70 29 5d 3b  [tuple(c,step)];
1090: 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66  .......} else if
10a0: 28 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 5b  (forbidden_cell[
10b0: 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 09 09 7d 20  y][x]){.......} 
10c0: 65 6c 73 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c  else if(g.map[y,
10d0: 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79  x]==' '||g.map[y
10e0: 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70  ,x]=='\\'||g.map
10f0: 5b 79 2c 78 5d 3d 3d 27 2e 27 29 20 7b 0a 09 09  [y,x]=='.') {...
1100: 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 50  .....q2 ~= new P
1110: 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 09  os(y,x);........
1120: 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09  v[y][x]=true;...
1130: 09 09 09 09 7d 0a 09 09 09 09 09 7d 0a 09 09 09  ....}......}....
1140: 09 7d 0a 09 09 09 09 71 20 3d 20 71 32 3b 0a 09  .}.....q = q2;..
1150: 09 09 7d 0a 09 09 09 72 65 74 75 72 6e 20 5b 5d  ..}....return []
1160: 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 70 75 73 68  ;...}....// push
1170: 20 72 6f 63 6b 73 21 0a 09 09 54 75 70 6c 65 21   rocks!...Tuple!
1180: 28 63 68 61 72 2c 69 6e 74 29 5b 5d 20 74 72 79  (char,int)[] try
1190: 43 28 29 20 7b 0a 09 09 09 63 6f 6e 73 74 28 50  C() {....const(P
11a0: 6f 73 29 5b 5d 20 71 3b 0a 09 09 09 66 6f 72 65  os)[] q;....fore
11b0: 61 63 68 28 70 3b 20 67 73 29 20 71 20 7e 3d 20  ach(p; gs) q ~= 
11c0: 70 3b 0a 09 09 09 62 6f 6f 6c 5b 5d 5b 5d 20 76  p;....bool[][] v
11d0: 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28   = new bool[][](
11e0: 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 70  g.map.H+2, g.map
11f0: 2e 57 2b 32 29 3b 0a 09 09 09 66 6f 72 65 61 63  .W+2);....foreac
1200: 68 28 70 3b 20 71 29 20 76 5b 70 2e 79 5d 5b 70  h(p; q) v[p.y][p
1210: 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 09 66 6f 72  .x]=true;....for
1220: 28 69 6e 74 20 73 74 65 70 3d 32 30 3b 20 71 2e  (int step=20; q.
1230: 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 29 20  length; ++step) 
1240: 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a  {.....Pos[] q2;.
1250: 09 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71  ....foreach(p; q
1260: 29 20 7b 0a 09 09 09 09 09 69 6e 74 5b 5d 20 64  ) {......int[] d
1270: 79 3d 5b 2d 31 2c 2b 31 2c 30 2c 30 5d 3b 0a 09  y=[-1,+1,0,0];..
1280: 09 09 09 09 69 6e 74 5b 5d 20 64 78 3d 5b 30 2c  ....int[] dx=[0,
1290: 30 2c 2d 31 2c 2b 31 5d 3b 0a 09 09 09 09 09 66  0,-1,+1];......f
12a0: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 34 3b  or(int i=0; i<4;
12b0: 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 09 69 6e   ++i) {.......in
12c0: 74 20 79 20 3d 20 70 2e 79 2b 64 79 5b 69 5d 3b  t y = p.y+dy[i];
12d0: 0a 09 09 09 09 09 09 69 6e 74 20 78 20 3d 20 70  .......int x = p
12e0: 2e 78 2b 64 78 5b 69 5d 3b 0a 09 09 09 09 09 09  .x+dx[i];.......
12f0: 69 66 28 76 5b 79 5d 5b 78 5d 29 20 63 6f 6e 74  if(v[y][x]) cont
1300: 69 6e 75 65 3b 0a 09 09 09 09 09 09 69 66 28 79  inue;.......if(y
1310: 3d 3d 73 2e 79 20 26 26 20 78 3d 3d 73 2e 78 29  ==s.y && x==s.x)
1320: 20 7b 0a 09 09 09 09 09 09 09 63 68 61 72 20 63   {........char c
1330: 20 3d 20 22 55 44 52 4c 22 5b 69 5d 3b 0a 09 09   = "UDRL"[i];...
1340: 09 09 09 09 09 69 66 28 20 64 65 61 74 68 2e 63  .....if( death.c
1350: 6f 75 6e 74 28 63 29 20 3d 3d 20 30 20 29 0a 09  ount(c) == 0 )..
1360: 09 09 09 09 09 09 09 72 65 74 75 72 6e 20 5b 74  .......return [t
1370: 75 70 6c 65 28 63 2c 73 74 65 70 29 5d 3b 0a 09  uple(c,step)];..
1380: 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 66  .....} else if(f
1390: 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 5b 79 5d  orbidden_cell[y]
13a0: 5b 78 5d 29 7b 0a 09 09 09 09 09 09 7d 20 65 6c  [x]){.......} el
13b0: 73 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d  se if(g.map[y,x]
13c0: 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78  ==' '||g.map[y,x
13d0: 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79  ]=='\\'||g.map[y
13e0: 2c 78 5d 3d 3d 27 2e 27 29 20 7b 0a 09 09 09 09  ,x]=='.') {.....
13f0: 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73  ...q2 ~= new Pos
1400: 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 09 76 5b  (y,x);........v[
1410: 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09 09  y][x]=true;.....
1420: 09 09 7d 20 65 6c 73 65 20 69 66 28 64 79 5b 69  ..} else if(dy[i
1430: 5d 3d 3d 30 20 26 26 20 67 2e 6d 61 70 5b 70 5d  ]==0 && g.map[p]
1440: 3d 3d 27 20 27 20 26 26 20 67 2e 6d 61 70 5b 79  ==' ' && g.map[y
1450: 2c 78 5d 3d 3d 27 2a 27 20 26 26 20 28 67 2e 6d  ,x]=='*' && (g.m
1460: 61 70 5b 79 2b 64 79 5b 69 5d 2c 78 2b 64 78 5b  ap[y+dy[i],x+dx[
1470: 69 5d 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b  i]]==' '||g.map[
1480: 79 2b 64 79 5b 69 5d 2c 78 2b 64 78 5b 69 5d 5d  y+dy[i],x+dx[i]]
1490: 3d 3d 27 52 27 29 29 20 7b 0a 09 09 09 09 09 09  =='R')) {.......
14a0: 09 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79  .q2 ~= new Pos(y
14b0: 2c 78 29 3b 0a 09 09 09 09 09 09 09 76 5b 79 5d  ,x);........v[y]
14c0: 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09 09 09 09  [x]=true;.......
14d0: 7d 0a 09 09 09 09 09 7d 0a 09 09 09 09 7d 0a 09  }......}.....}..
14e0: 09 09 09 71 20 3d 20 71 32 3b 0a 09 09 09 7d 0a  ...q = q2;....}.
14f0: 09 09 09 72 65 74 75 72 6e 20 5b 5d 3b 0a 09 09  ...return [];...
1500: 7d 0a 09 09 72 65 74 75 72 6e 20 28 64 61 6e 67  }...return (dang
1510: 65 72 5f 6f 6b 20 3f 20 5b 5d 20 3a 20 74 72 79  er_ok ? [] : try
1520: 41 28 29 29 20 7e 20 74 72 79 42 28 29 20 7e 20  A()) ~ tryB() ~ 
1530: 74 72 79 43 28 29 3b 0a 09 7d 0a 7d 0a 0a 61 6c  tryC();..}.}..al
1540: 69 61 73 20 53 6f 6c 76 65 72 5f 31 20 4d 61 69  ias Solver_1 Mai
1550: 6e 53 6f 6c 76 65 72 3b 0a                       nSolver;.