0000: 2f 2f 0a 2f 2f 20 68 74 74 70 3a 2f 2f 65 6e 2e //.// http://en.
0010: 77 69 6b 69 70 65 64 69 61 2e 6f 72 67 2f 77 69 wikipedia.org/wi
0020: 6b 69 2f 46 25 43 35 25 41 42 72 69 6e 6b 61 7a ki/F%C5%ABrinkaz
0030: 61 6e 0a 2f 2f 0a 69 6d 70 6f 72 74 20 75 74 69 an.//.import uti
0040: 6c 3b 0a 69 6d 70 6f 72 74 20 67 61 6d 65 3b 0a l;.import game;.
0050: 0a 62 6f 6f 6c 20 69 73 5f 73 70 61 63 79 28 63 .bool is_spacy(c
0060: 68 61 72 20 63 29 0a 7b 0a 09 72 65 74 75 72 6e har c).{..return
0070: 20 63 3d 3d 27 20 27 20 7c 7c 20 63 3d 3d 27 2e c==' ' || c=='.
0080: 27 20 7c 7c 20 63 3d 3d 27 52 27 20 7c 7c 20 63 ' || c=='R' || c
0090: 3d 3d 27 21 27 20 7c 7c 20 63 3d 3d 27 5c 5c 27 =='!' || c=='\\'
00a0: 20 7c 7c 20 63 3d 3d 27 4f 27 3b 0a 7d 0a 0a 62 || c=='O';.}..b
00b0: 6f 6f 6c 20 69 73 5f 72 6f 63 6b 79 28 63 68 61 ool is_rocky(cha
00c0: 72 20 63 29 0a 7b 0a 09 72 65 74 75 72 6e 20 63 r c).{..return c
00d0: 3d 3d 27 2a 27 20 7c 7c 20 63 3d 3d 27 40 27 3b =='*' || c=='@';
00e0: 0a 7d 0a 0a 62 6f 6f 6c 20 69 73 5f 74 72 75 65 .}..bool is_true
00f0: 5f 73 70 61 63 65 28 63 68 61 72 20 63 29 0a 7b _space(char c).{
0100: 0a 09 72 65 74 75 72 6e 20 63 3d 3d 27 20 27 3b ..return c==' ';
0110: 0a 7d 0a 0a 62 6f 6f 6c 20 69 73 5f 74 72 61 6d .}..bool is_tram
0120: 70 6f 6c 69 6e 65 5f 73 6f 75 72 63 65 28 63 68 poline_source(ch
0130: 61 72 20 63 29 0a 7b 0a 09 72 65 74 75 72 6e 20 ar c).{..return
0140: 27 41 27 3c 3d 63 20 26 26 20 63 3c 3d 27 49 27 'A'<=c && c<='I'
0150: 3b 0a 7d 0a 0a 62 6f 6f 6c 20 69 73 5f 72 6f 63 ;.}..bool is_roc
0160: 6b 6c 61 6d 62 64 61 28 63 68 61 72 20 63 29 0a klambda(char c).
0170: 7b 0a 09 72 65 74 75 72 6e 20 69 73 5f 72 6f 63 {..return is_roc
0180: 6b 79 28 63 29 20 7c 7c 20 63 3d 3d 27 5c 5c 27 ky(c) || c=='\\'
0190: 3b 0a 7d 0a 0a 54 75 70 6c 65 21 28 73 74 72 69 ;.}..Tuple!(stri
01a0: 6e 67 2c 69 6e 74 29 20 64 65 61 74 68 5f 6d 6f ng,int) death_mo
01b0: 76 65 28 69 6e 20 47 61 6d 65 20 67 29 0a 7b 0a ve(in Game g).{.
01c0: 09 2f 2f 20 54 4f 44 4f 3a 20 53 0a 0a 09 73 74 .// TODO: S...st
01d0: 72 69 6e 67 20 64 65 61 74 68 3b 0a 09 69 6e 74 ring death;..int
01e0: 20 62 72 65 61 74 68 3b 0a 09 69 6e 74 20 79 20 breath;..int y
01f0: 3d 20 67 2e 6d 61 70 2e 72 6f 62 6f 74 2e 79 3b = g.map.robot.y;
0200: 0a 09 69 6e 74 20 78 20 3d 20 67 2e 6d 61 70 2e ..int x = g.map.
0210: 72 6f 62 6f 74 2e 78 3b 0a 09 69 6e 74 5b 35 5d robot.x;..int[5]
0220: 20 64 79 5f 3d 5b 2b 31 2c 2d 31 2c 30 2c 30 2c dy_=[+1,-1,0,0,
0230: 30 5d 3b 0a 09 69 6e 74 5b 35 5d 20 64 78 5f 3d 0];..int[5] dx_=
0240: 5b 30 2c 30 2c 2d 31 2c 2b 31 2c 30 5d 3b 0a 09 [0,0,-1,+1,0];..
0250: 63 68 61 72 5b 5d 20 64 73 3d 5b 27 55 27 2c 27 char[] ds=['U','
0260: 44 27 2c 27 4c 27 2c 27 52 27 2c 27 57 27 5d 3b D','L','R','W'];
0270: 0a 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0280: 3c 35 3b 20 2b 2b 69 29 0a 09 7b 0a 09 09 62 6f <5; ++i)..{...bo
0290: 6f 6c 20 61 66 74 65 72 5f 6d 6f 76 65 5f 64 65 ol after_move_de
02a0: 61 74 68 28 69 6e 74 20 79 2c 20 69 6e 74 20 78 ath(int y, int x
02b0: 2c 20 63 68 61 72 20 74 72 5f 74 67 74 29 0a 09 , char tr_tgt)..
02c0: 09 7b 0a 09 09 09 62 6f 6f 6c 20 69 73 5f 73 70 .{....bool is_sp
02d0: 61 63 79 5f 74 28 63 68 61 72 20 63 29 20 7b 0a acy_t(char c) {.
02e0: 09 09 09 09 69 66 28 69 73 5f 74 72 75 65 5f 73 ....if(is_true_s
02f0: 70 61 63 65 28 63 29 20 7c 7c 20 63 3d 3d 27 52 pace(c) || c=='R
0300: 27 20 7c 7c 20 63 3d 3d 74 72 5f 74 67 74 29 0a ' || c==tr_tgt).
0310: 09 09 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 .....return true
0320: 3b 0a 09 09 09 09 72 65 74 75 72 6e 20 28 27 41 ;.....return ('A
0330: 27 3c 3d 63 20 26 26 20 63 3c 3d 27 49 27 20 26 '<=c && c<='I' &
0340: 26 20 67 2e 74 72 2e 74 61 72 67 65 74 5f 6f 66 & g.tr.target_of
0350: 28 63 29 3d 3d 74 72 5f 74 67 74 29 3b 0a 09 09 (c)==tr_tgt);...
0360: 09 7d 0a 0a 09 09 09 2f 2f 20 63 68 65 63 6b 20 .}.....// check
0370: 77 61 74 65 72 0a 09 09 09 69 66 28 20 67 2e 6d water....if( g.m
0380: 61 70 5b 79 2c 78 5d 21 3d 27 4f 27 20 26 26 20 ap[y,x]!='O' &&
0390: 67 2e 68 70 3d 3d 30 20 26 26 20 79 3c 3d 67 2e g.hp==0 && y<=g.
03a0: 77 61 74 65 72 5f 6c 65 76 65 6c 20 29 0a 09 09 water_level )...
03b0: 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b 0a 0a ..return true;..
03c0: 09 09 09 2f 2f 20 63 68 65 63 6b 20 66 61 6c 6c ...// check fall
03d0: 69 6e 67 20 72 6f 63 6b 2e 0a 09 09 09 69 6e 74 ing rock.....int
03e0: 20 79 79 3d 79 2b 31 2c 20 78 78 3d 78 3b 0a 09 yy=y+1, xx=x;..
03f0: 09 09 69 66 28 20 69 73 5f 73 70 61 63 79 5f 74 ..if( is_spacy_t
0400: 28 67 2e 6d 61 70 5b 79 79 2c 20 78 78 5d 29 20 (g.map[yy, xx])
0410: 29 0a 09 09 09 7b 0a 09 09 09 09 69 66 28 20 69 )....{.....if( i
0420: 73 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 5b 79 79 s_rocky(g.map[yy
0430: 2b 31 2c 78 78 5d 29 20 29 0a 09 09 09 09 09 72 +1,xx]) )......r
0440: 65 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 09 eturn true;.....
0450: 69 66 28 20 69 73 5f 73 70 61 63 79 5f 74 28 67 if( is_spacy_t(g
0460: 2e 6d 61 70 5b 79 79 2b 31 2c 78 78 5d 29 20 26 .map[yy+1,xx]) &
0470: 26 20 69 73 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 & is_rocky(g.map
0480: 5b 79 79 2b 31 2c 78 78 2b 31 5d 29 20 26 26 20 [yy+1,xx+1]) &&
0490: 69 73 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 5b 79 is_rocky(g.map[y
04a0: 79 2c 78 78 2b 31 5d 29 20 29 20 7b 0a 09 09 09 y,xx+1]) ) {....
04b0: 09 09 69 66 28 20 69 73 5f 73 70 61 63 79 5f 74 ..if( is_spacy_t
04c0: 28 67 2e 6d 61 70 5b 79 79 2b 31 2c 78 78 2b 32 (g.map[yy+1,xx+2
04d0: 5d 29 20 26 26 20 69 73 5f 73 70 61 63 79 5f 74 ]) && is_spacy_t
04e0: 28 67 2e 6d 61 70 5b 79 79 2c 78 78 2b 32 5d 29 (g.map[yy,xx+2])
04f0: 20 29 0a 09 09 09 09 09 09 72 65 74 75 72 6e 20 ).......return
0500: 66 61 6c 73 65 3b 0a 09 09 09 09 09 72 65 74 75 false;......retu
0510: 72 6e 20 74 72 75 65 3b 0a 09 09 09 09 7d 0a 09 rn true;.....}..
0520: 09 09 09 69 66 28 20 69 73 5f 73 70 61 63 79 5f ...if( is_spacy_
0530: 74 28 67 2e 6d 61 70 5b 79 79 2b 31 2c 78 78 5d t(g.map[yy+1,xx]
0540: 29 20 26 26 20 69 73 5f 72 6f 63 6b 79 28 67 2e ) && is_rocky(g.
0550: 6d 61 70 5b 79 79 2b 31 2c 78 78 2d 31 5d 29 20 map[yy+1,xx-1])
0560: 26 26 20 69 73 5f 72 6f 63 6b 6c 61 6d 62 64 61 && is_rocklambda
0570: 28 67 2e 6d 61 70 5b 79 79 2c 78 78 2d 31 5d 29 (g.map[yy,xx-1])
0580: 20 29 20 7b 0a 09 09 09 09 09 69 66 28 67 2e 68 ) {......if(g.h
0590: 69 67 65 5f 75 6e 74 69 6c 5f 72 69 73 65 20 3d ige_until_rise =
05a0: 3d 20 31 20 26 26 20 67 2e 6d 61 70 5b 79 79 2b = 1 && g.map[yy+
05b0: 31 2c 78 78 2b 31 5d 3d 3d 27 57 27 29 0a 09 09 1,xx+1]=='W')...
05c0: 09 09 09 09 72 65 74 75 72 6e 20 66 61 6c 73 65 ....return false
05d0: 3b 0a 09 09 09 09 09 72 65 74 75 72 6e 20 74 72 ;......return tr
05e0: 75 65 3b 0a 09 09 09 09 7d 0a 09 09 09 7d 0a 09 ue;.....}....}..
05f0: 09 09 72 65 74 75 72 6e 20 66 61 6c 73 65 3b 0a ..return false;.
0600: 09 09 7d 0a 0a 09 09 69 6e 74 20 64 79 3d 64 79 ..}....int dy=dy
0610: 5f 5b 69 5d 2c 20 64 78 3d 64 78 5f 5b 69 5d 3b _[i], dx=dx_[i];
0620: 0a 09 09 69 66 28 20 69 73 5f 73 70 61 63 79 28 ...if( is_spacy(
0630: 67 2e 6d 61 70 5b 79 2b 64 79 2c 78 2b 64 78 5d g.map[y+dy,x+dx]
0640: 29 20 7c 7c 20 64 79 3d 3d 30 20 26 26 20 69 73 ) || dy==0 && is
0650: 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 5b 79 2c 78 _rocky(g.map[y,x
0660: 2b 64 78 5d 29 20 26 26 20 69 73 5f 74 72 75 65 +dx]) && is_true
0670: 5f 73 70 61 63 65 28 67 2e 6d 61 70 5b 79 2c 78 _space(g.map[y,x
0680: 2b 32 2a 64 78 5d 29 20 29 0a 09 09 7b 0a 09 09 +2*dx]) )...{...
0690: 09 69 66 28 20 61 66 74 65 72 5f 6d 6f 76 65 5f .if( after_move_
06a0: 64 65 61 74 68 28 79 2b 64 79 2c 20 78 2b 64 78 death(y+dy, x+dx
06b0: 2c 20 63 68 61 72 2e 69 6e 69 74 29 20 29 0a 09 , char.init) )..
06c0: 09 09 09 64 65 61 74 68 20 7e 3d 20 64 73 5b 69 ...death ~= ds[i
06d0: 5d 3b 0a 09 09 09 65 6c 73 65 20 69 66 28 64 73 ];....else if(ds
06e0: 5b 69 5d 20 21 3d 20 27 57 27 29 0a 09 09 09 09 [i] != 'W').....
06f0: 62 72 65 61 74 68 20 2b 2b 3b 0a 09 09 7d 0a 09 breath ++;...}..
0700: 09 65 6c 73 65 20 69 66 28 20 69 73 5f 74 72 61 .else if( is_tra
0710: 6d 70 6f 6c 69 6e 65 5f 73 6f 75 72 63 65 28 67 mpoline_source(g
0720: 2e 6d 61 70 5b 79 2b 64 79 2c 78 2b 64 78 5d 29 .map[y+dy,x+dx])
0730: 20 29 0a 09 09 7b 0a 09 09 09 50 6f 73 20 70 20 )...{....Pos p
0740: 3d 20 67 2e 74 72 2e 74 61 72 67 65 74 5f 70 6f = g.tr.target_po
0750: 73 28 67 2e 6d 61 70 5b 79 2b 64 79 2c 78 2b 64 s(g.map[y+dy,x+d
0760: 78 5d 29 3b 0a 09 09 09 69 66 28 20 61 66 74 65 x]);....if( afte
0770: 72 5f 6d 6f 76 65 5f 64 65 61 74 68 28 70 2e 79 r_move_death(p.y
0780: 2c 20 70 2e 78 2c 20 67 2e 74 72 2e 74 61 72 67 , p.x, g.tr.targ
0790: 65 74 5f 6f 66 28 67 2e 6d 61 70 5b 79 2b 64 79 et_of(g.map[y+dy
07a0: 2c 78 2b 64 78 5d 29 29 20 29 0a 09 09 09 09 64 ,x+dx])) ).....d
07b0: 65 61 74 68 20 7e 3d 20 64 73 5b 69 5d 3b 0a 09 eath ~= ds[i];..
07c0: 09 09 65 6c 73 65 0a 09 09 09 09 62 72 65 61 74 ..else.....breat
07d0: 68 20 2b 2b 3b 0a 09 09 7d 0a 09 09 65 6c 73 65 h ++;...}...else
07e0: 0a 09 09 7b 0a 09 09 09 64 65 61 74 68 20 7e 3d ...{....death ~=
07f0: 20 64 73 5b 69 5d 3b 0a 09 09 7d 0a 09 7d 0a 0a ds[i];...}..}..
0800: 09 72 65 74 75 72 6e 20 74 75 70 6c 65 28 64 65 .return tuple(de
0810: 61 74 68 2c 20 62 72 65 61 74 68 29 3b 0a 7d 0a ath, breath);.}.
0820: 0a 69 6e 74 65 72 66 61 63 65 20 53 6f 6c 76 65 .interface Solve
0830: 72 0a 7b 0a 09 2f 2f 20 74 68 69 73 28 69 6e 20 r.{..// this(in
0840: 47 61 6d 65 20 67 29 3b 0a 09 63 68 61 72 20 73 Game g);..char s
0850: 69 6e 67 6c 65 5f 73 74 65 70 28 29 3b 0a 09 76 ingle_step();..v
0860: 6f 69 64 20 66 6f 72 63 65 28 63 68 61 72 20 63 oid force(char c
0870: 29 3b 0a 7d 0a 0a 63 6c 61 73 73 20 e4 b8 8d e5 );.}..class ....
0880: 8b 95 e5 a6 82 e5 b1 b1 20 3a 20 53 6f 6c 76 65 ........ : Solve
0890: 72 0a 7b 0a 09 74 68 69 73 28 69 6e 20 47 61 6d r.{..this(in Gam
08a0: 65 20 67 29 20 7b 7d 0a 09 63 68 61 72 20 73 69 e g) {}..char si
08b0: 6e 67 6c 65 5f 73 74 65 70 28 29 20 7b 20 72 65 ngle_step() { re
08c0: 74 75 72 6e 20 27 57 27 3b 20 7d 0a 09 76 6f 69 turn 'W'; }..voi
08d0: 64 20 66 6f 72 63 65 28 63 68 61 72 20 63 29 20 d force(char c)
08e0: 7b 7d 0a 7d 0a 0a 63 6c 61 73 73 20 e5 be 90 e5 {}.}..class ....
08f0: a6 82 e6 9e 97 20 3a 20 53 6f 6c 76 65 72 0a 7b ..... : Solver.{
0900: 0a 09 69 6e 74 20 77 61 69 74 5f 63 6f 75 6e 74 ..int wait_count
0910: 20 3d 20 30 3b 0a 09 69 6e 74 20 63 68 6f 6b 65 = 0;..int choke
0920: 5f 63 6f 75 6e 74 20 3d 20 30 3b 0a 0a 09 47 61 _count = 0;...Ga
0930: 6d 65 20 67 3b 0a 09 74 68 69 73 28 69 6e 20 47 me g;..this(in G
0940: 61 6d 65 20 67 29 0a 09 7b 0a 09 09 74 68 69 73 ame g)..{...this
0950: 2e 67 20 3d 20 67 2e 63 6c 6f 6e 65 28 29 3b 0a .g = g.clone();.
0960: 09 09 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c ..forbidden_cell
0970: 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 = new bool[][](
0980: 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 g.map.H+2, g.map
0990: 2e 57 2b 32 29 3b 0a 09 7d 0a 0a 09 63 68 61 72 .W+2);..}...char
09a0: 20 73 69 6e 67 6c 65 5f 73 74 65 70 28 29 0a 09 single_step()..
09b0: 7b 0a 09 09 54 75 70 6c 65 21 28 73 74 72 69 6e {...Tuple!(strin
09c0: 67 2c 69 6e 74 29 20 64 65 20 3d 20 64 65 61 74 g,int) de = deat
09d0: 68 5f 6d 6f 76 65 28 67 29 3b 0a 09 09 63 68 61 h_move(g);...cha
09e0: 72 20 63 20 3d 20 61 63 74 28 67 2c 20 64 65 5b r c = act(g, de[
09f0: 30 5d 2c 20 64 65 5b 31 5d 29 3b 0a 09 09 66 6f 0], de[1]);...fo
0a00: 72 63 65 28 63 29 3b 0a 09 09 72 65 74 75 72 6e rce(c);...return
0a10: 20 63 3b 0a 09 7d 0a 0a 09 76 6f 69 64 20 66 6f c;..}...void fo
0a20: 72 63 65 28 63 68 61 72 20 63 29 0a 09 7b 0a 09 rce(char c)..{..
0a30: 09 69 66 28 63 20 21 3d 20 27 41 27 29 0a 09 09 .if(c != 'A')...
0a40: 09 67 2e 63 6f 6d 6d 61 6e 64 28 63 29 3b 0a 09 .g.command(c);..
0a50: 7d 0a 0a 09 54 75 70 6c 65 21 28 50 6f 73 2c 20 }...Tuple!(Pos,
0a60: 69 6e 74 29 5b 5d 20 6c 6f 67 3b 0a 09 62 6f 6f int)[] log;..boo
0a70: 6c 5b 5d 5b 5d 20 66 6f 72 62 69 64 64 65 6e 5f l[][] forbidden_
0a80: 63 65 6c 6c 3b 0a 0a 09 63 68 61 72 20 61 63 74 cell;...char act
0a90: 28 63 6f 6e 73 74 28 47 61 6d 65 29 20 67 2c 20 (const(Game) g,
0aa0: 73 74 72 69 6e 67 20 64 65 61 74 68 2c 20 69 6e string death, in
0ab0: 74 20 62 72 65 61 74 68 29 0a 09 7b 0a 09 09 63 t breath)..{...c
0ac0: 6f 6e 73 74 20 50 6f 73 20 20 20 20 72 6f 20 3d onst Pos ro =
0ad0: 20 67 2e 6d 61 70 2e 72 6f 62 6f 74 3b 0a 09 09 g.map.robot;...
0ae0: 63 6f 6e 73 74 20 50 6f 73 20 20 20 20 6c 69 20 const Pos li
0af0: 3d 20 67 2e 6d 61 70 2e 6c 69 66 74 3b 0a 09 09 = g.map.lift;...
0b00: 50 6f 73 5b 5d 20 6c 61 20 3d 20 67 2e 6d 61 70 Pos[] la = g.map
0b10: 2e 6c 61 6d 62 64 61 73 28 29 3b 0a 09 09 73 6f .lambdas();...so
0b20: 72 74 21 28 28 50 6f 73 20 61 2c 50 6f 73 20 62 rt!((Pos a,Pos b
0b30: 29 7b 0a 09 09 09 69 6e 74 20 61 64 3d 61 62 73 ){....int ad=abs
0b40: 28 61 2e 79 2d 6c 69 2e 79 29 2b 61 62 73 28 61 (a.y-li.y)+abs(a
0b50: 2e 78 2d 6c 69 2e 78 29 3b 0a 09 09 09 69 6e 74 .x-li.x);....int
0b60: 20 62 64 3d 61 62 73 28 62 2e 79 2d 6c 69 2e 79 bd=abs(b.y-li.y
0b70: 29 2b 61 62 73 28 62 2e 78 2d 6c 69 2e 78 29 3b )+abs(b.x-li.x);
0b80: 0a 09 09 09 72 65 74 75 72 6e 20 61 64 3e 62 64 ....return ad>bd
0b90: 3b 3b 0a 09 09 7d 29 28 6c 61 29 3b 0a 09 09 50 ;;...})(la);...P
0ba0: 6f 73 5b 5d 20 72 61 20 3d 20 67 2e 6d 61 70 2e os[] ra = g.map.
0bb0: 72 61 7a 6f 72 73 28 29 3b 0a 09 09 63 6f 6e 73 razors();...cons
0bc0: 74 28 50 6f 73 29 5b 5d 20 68 69 20 3d 20 67 2e t(Pos)[] hi = g.
0bd0: 6d 61 70 2e 6f 62 6a 65 63 74 73 28 27 57 27 29 map.objects('W')
0be0: 3b 0a 0a 09 09 54 75 70 6c 65 21 28 63 68 61 72 ;....Tuple!(char
0bf0: 2c 69 6e 74 29 5b 5d 20 63 61 6e 64 3b 0a 09 09 ,int)[] cand;...
0c00: 63 68 61 72 20 63 20 3d 20 27 57 27 3b 0a 09 09 char c = 'W';...
0c10: 69 66 28 20 67 2e 6d 61 70 2e 63 6f 6c 6c 65 63 if( g.map.collec
0c20: 74 65 64 5f 6c 61 6d 62 64 61 20 3d 3d 20 67 2e ted_lambda == g.
0c30: 6d 61 70 2e 74 6f 74 61 6c 5f 6c 61 6d 62 64 61 map.total_lambda
0c40: 20 29 20 7b 0a 09 09 09 63 61 6e 64 20 3d 20 73 ) {....cand = s
0c50: 65 61 72 63 68 28 67 2c 20 72 6f 2c 20 5b 6c 69 earch(g, ro, [li
0c60: 5d 2c 20 64 65 61 74 68 29 3b 0a 09 09 7d 20 65 ], death);...} e
0c70: 6c 73 65 20 69 66 28 20 21 6c 61 2e 65 6d 70 74 lse if( !la.empt
0c80: 79 20 29 7b 0a 09 09 09 63 61 6e 64 20 7e 3d 20 y ){....cand ~=
0c90: 73 65 61 72 63 68 28 67 2c 20 72 6f 2c 20 6c 61 search(g, ro, la
0ca0: 7e 72 61 2c 20 64 65 61 74 68 29 3b 0a 09 09 7d ~ra, death);...}
0cb0: 0a 0a 09 09 2f 2f 20 27 68 69 67 65 73 6f 72 69 ....// 'higesori
0cc0: 27 20 6d 6f 64 65 0a 09 09 69 66 28 20 21 68 69 ' mode...if( !hi
0cd0: 2e 65 6d 70 74 79 20 26 26 20 67 2e 6d 61 70 2e .empty && g.map.
0ce0: 72 61 7a 6f 72 3e 30 20 29 20 7b 0a 09 09 09 69 razor>0 ) {....i
0cf0: 6e 74 20 68 69 73 20 3d 20 30 3b 0a 09 09 09 66 nt his = 0;....f
0d00: 6f 72 28 69 6e 74 20 64 79 3d 2d 31 3b 20 64 79 or(int dy=-1; dy
0d10: 3c 3d 2b 31 3b 20 2b 2b 64 79 29 0a 09 09 09 66 <=+1; ++dy)....f
0d20: 6f 72 28 69 6e 74 20 64 78 3d 2d 31 3b 20 64 78 or(int dx=-1; dx
0d30: 3c 3d 2b 31 3b 20 2b 2b 64 78 29 0a 09 09 09 09 <=+1; ++dx).....
0d40: 69 66 28 67 2e 6d 61 70 5b 72 6f 2e 79 2b 64 79 if(g.map[ro.y+dy
0d50: 2c 72 6f 2e 78 2b 64 78 5d 20 3d 3d 20 27 57 27 ,ro.x+dx] == 'W'
0d60: 29 0a 09 09 09 09 09 68 69 73 2b 2b 3b 0a 0a 09 )......his++;...
0d70: 09 09 69 66 28 68 69 73 3e 3d 32 20 7c 7c 20 68 ..if(his>=2 || h
0d80: 69 73 3d 3d 68 69 2e 6c 65 6e 67 74 68 29 0a 09 is==hi.length)..
0d90: 09 09 09 63 61 6e 64 20 3d 20 5b 74 75 70 6c 65 ...cand = [tuple
0da0: 28 27 53 27 2c 69 6e 74 2e 6d 61 78 29 5d 3b 0a ('S',int.max)];.
0db0: 09 09 09 69 66 28 63 61 6e 64 2e 65 6d 70 74 79 ...if(cand.empty
0dc0: 29 20 7b 0a 09 09 09 09 63 6f 6e 73 74 28 50 6f ) {.....const(Po
0dd0: 73 29 5b 5d 20 74 67 74 3b 0a 09 09 09 09 66 6f s)[] tgt;.....fo
0de0: 72 28 69 6e 74 20 79 3d 31 3b 20 79 3c 3d 67 2e r(int y=1; y<=g.
0df0: 6d 61 70 2e 48 3b 20 2b 2b 79 29 0a 09 09 09 09 map.H; ++y).....
0e00: 66 6f 72 28 69 6e 74 20 78 3d 31 3b 20 78 3c 3d for(int x=1; x<=
0e10: 67 2e 6d 61 70 2e 57 3b 20 2b 2b 78 29 0a 09 09 g.map.W; ++x)...
0e20: 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d ...if(g.map[y,x]
0e30: 3d 3d 27 2e 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 =='.'||g.map[y,x
0e40: 5d 3d 3d 27 20 27 29 20 7b 0a 09 09 09 09 09 09 ]==' ') {.......
0e50: 68 69 73 20 3d 20 30 3b 0a 09 09 09 09 09 09 66 his = 0;.......f
0e60: 6f 72 28 69 6e 74 20 64 79 3d 2d 31 3b 20 64 79 or(int dy=-1; dy
0e70: 3c 3d 2b 31 3b 20 2b 2b 64 79 29 0a 09 09 09 09 <=+1; ++dy).....
0e80: 09 09 66 6f 72 28 69 6e 74 20 64 78 3d 2d 31 3b ..for(int dx=-1;
0e90: 20 64 78 3c 3d 2b 31 3b 20 2b 2b 64 78 29 0a 09 dx<=+1; ++dx)..
0ea0: 09 09 09 09 09 09 69 66 28 67 2e 6d 61 70 5b 79 ......if(g.map[y
0eb0: 2b 64 79 2c 78 2b 64 78 5d 20 3d 3d 20 27 57 27 +dy,x+dx] == 'W'
0ec0: 29 0a 09 09 09 09 09 09 09 09 68 69 73 2b 2b 3b ).........his++;
0ed0: 0a 09 09 09 09 09 09 69 66 28 68 69 73 3e 3d 32 .......if(his>=2
0ee0: 29 0a 09 09 09 09 09 09 09 74 67 74 20 7e 3d 20 )........tgt ~=
0ef0: 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09 new Pos(y,x);...
0f00: 09 09 09 7d 0a 09 09 09 09 63 61 6e 64 20 7e 3d ...}.....cand ~=
0f10: 20 73 65 61 72 63 68 28 67 2c 20 72 6f 2c 20 74 search(g, ro, t
0f20: 67 74 2c 20 64 65 61 74 68 2c 20 74 72 75 65 29 gt, death, true)
0f30: 3b 0a 09 09 09 7d 0a 09 09 7d 0a 0a 09 09 2f 2f ;....}...}....//
0f40: 20 27 64 69 67 27 20 6d 6f 64 65 0a 09 09 69 66 'dig' mode...if
0f50: 28 63 61 6e 64 2e 65 6d 70 74 79 29 20 7b 0a 09 (cand.empty) {..
0f60: 09 09 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20 74 ..const(Pos)[] t
0f70: 67 74 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 79 gt;....for(int y
0f80: 3d 31 3b 20 79 3c 3d 67 2e 6d 61 70 2e 48 3b 20 =1; y<=g.map.H;
0f90: 2b 2b 79 29 0a 09 09 09 66 6f 72 28 69 6e 74 20 ++y)....for(int
0fa0: 78 3d 31 3b 20 78 3c 3d 67 2e 6d 61 70 2e 57 3b x=1; x<=g.map.W;
0fb0: 20 2b 2b 78 29 0a 09 09 09 09 69 66 28 67 2e 6d ++x).....if(g.m
0fc0: 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27 29 0a 09 09 ap[y,x]=='.')...
0fd0: 09 09 09 69 66 28 69 73 5f 72 6f 63 6b 79 28 67 ...if(is_rocky(g
0fe0: 2e 6d 61 70 5b 79 2b 31 2c 78 5d 29 7c 7c 69 73 .map[y+1,x])||is
0ff0: 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 5b 79 2b 31 _rocky(g.map[y+1
1000: 2c 78 2d 31 5d 29 7c 7c 69 73 5f 72 6f 63 6b 79 ,x-1])||is_rocky
1010: 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 2b 31 5d 29 (g.map[y+1,x+1])
1020: 0a 09 09 09 09 09 20 7c 7c 69 73 5f 72 6f 63 6b ...... ||is_rock
1030: 79 28 67 2e 6d 61 70 5b 79 2c 78 2b 31 5d 29 7c y(g.map[y,x+1])|
1040: 7c 69 73 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 5b |is_rocky(g.map[
1050: 79 2c 78 2d 31 5d 29 29 0a 09 09 09 09 09 09 74 y,x-1])).......t
1060: 67 74 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c gt ~= new Pos(y,
1070: 78 29 3b 0a 09 09 09 63 61 6e 64 20 7e 3d 20 73 x);....cand ~= s
1080: 65 61 72 63 68 28 67 2c 20 72 6f 2c 20 74 67 74 earch(g, ro, tgt
1090: 2c 20 64 65 61 74 68 2c 20 74 72 75 65 29 3b 0a , death, true);.
10a0: 09 09 7d 0a 0a 09 09 69 66 28 63 61 6e 64 2e 65 ..}....if(cand.e
10b0: 6d 70 74 79 29 20 7b 0a 09 09 09 63 68 6f 6b 65 mpty) {....choke
10c0: 5f 63 6f 75 6e 74 2b 2b 3b 0a 09 09 09 63 61 6e _count++;....can
10d0: 64 20 7e 3d 20 74 75 70 6c 65 28 27 57 27 2c 69 d ~= tuple('W',i
10e0: 6e 74 2e 6d 61 78 29 3b 0a 09 09 7d 0a 09 09 73 nt.max);...}...s
10f0: 6f 72 74 21 28 28 54 75 70 6c 65 21 28 63 68 61 ort!((Tuple!(cha
1100: 72 2c 69 6e 74 29 20 63 31 2c 20 54 75 70 6c 65 r,int) c1, Tuple
1110: 21 28 63 68 61 72 2c 69 6e 74 29 20 63 32 29 7b !(char,int) c2){
1120: 0a 09 09 09 69 66 28 63 31 5b 31 5d 20 21 3d 20 ....if(c1[1] !=
1130: 63 32 5b 31 5d 29 0a 09 09 09 09 72 65 74 75 72 c2[1]).....retur
1140: 6e 20 63 31 5b 31 5d 20 3c 20 63 32 5b 31 5d 3b n c1[1] < c2[1];
1150: 0a 09 09 09 72 65 74 75 72 6e 20 63 31 5b 30 5d ....return c1[0]
1160: 20 3c 20 63 32 5b 30 5d 3b 0a 09 09 7d 29 28 63 < c2[0];...})(c
1170: 61 6e 64 29 3b 0a 09 09 63 20 3d 20 63 61 6e 64 and);...c = cand
1180: 5b 30 5d 5b 30 5d 3b 0a 0a 09 09 69 66 28 64 65 [0][0];....if(de
1190: 61 74 68 2e 63 6f 75 6e 74 28 63 29 20 7c 7c 20 ath.count(c) ||
11a0: 77 61 69 74 5f 63 6f 75 6e 74 3e 3d 32 29 20 7b wait_count>=2) {
11b0: 0a 09 09 09 66 6f 72 65 61 63 68 28 63 68 61 72 ....foreach(char
11c0: 20 6c 69 76 65 3b 20 22 55 44 4c 52 57 22 29 0a live; "UDLRW").
11d0: 09 09 09 09 69 66 28 64 65 61 74 68 2e 63 6f 75 ....if(death.cou
11e0: 6e 74 28 6c 69 76 65 29 3d 3d 30 29 20 7b 0a 09 nt(live)==0) {..
11f0: 09 09 09 09 63 3d 6c 69 76 65 3b 0a 09 09 09 09 ....c=live;.....
1200: 09 62 72 65 61 6b 3b 0a 09 09 09 09 7d 0a 09 09 .break;.....}...
1210: 7d 0a 0a 09 09 69 66 28 63 20 3d 3d 20 27 57 27 }....if(c == 'W'
1220: 29 0a 09 09 09 77 61 69 74 5f 63 6f 75 6e 74 2b )....wait_count+
1230: 2b 3b 0a 09 09 65 6c 73 65 0a 09 09 09 77 61 69 +;...else....wai
1240: 74 5f 63 6f 75 6e 74 20 3d 20 30 3b 0a 09 09 69 t_count = 0;...i
1250: 66 28 77 61 69 74 5f 63 6f 75 6e 74 3d 3d 32 29 f(wait_count==2)
1260: 0a 09 09 09 63 20 3d 20 27 41 27 3b 0a 09 09 69 ....c = 'A';...i
1270: 66 28 63 68 6f 6b 65 5f 63 6f 75 6e 74 20 3e 3d f(choke_count >=
1280: 20 67 2e 6d 61 70 2e 48 29 0a 09 09 09 63 20 3d g.map.H)....c =
1290: 20 27 41 27 3b 0a 0a 09 09 62 6f 6f 6c 5b 63 68 'A';....bool[ch
12a0: 61 72 5d 20 63 68 6f 69 63 65 3b 0a 09 09 66 6f ar] choice;...fo
12b0: 72 65 61 63 68 28 74 3b 20 63 61 6e 64 29 0a 09 reach(t; cand)..
12c0: 09 09 63 68 6f 69 63 65 5b 74 5b 30 5d 5d 20 3d ..choice[t[0]] =
12d0: 20 74 72 75 65 3b 0a 09 09 6c 6f 67 20 7e 3d 20 true;...log ~=
12e0: 74 75 70 6c 65 28 72 6f 2e 63 6c 6f 6e 65 28 29 tuple(ro.clone()
12f0: 2c 20 63 61 73 74 28 69 6e 74 29 63 68 6f 69 63 , cast(int)choic
1300: 65 2e 6c 65 6e 67 74 68 29 3b 0a 09 09 69 66 28 e.length);...if(
1310: 6c 6f 67 2e 6c 65 6e 67 74 68 20 3e 20 35 29 0a log.length > 5).
1320: 09 09 09 6c 6f 67 20 3d 20 6c 6f 67 5b 24 2d 35 ...log = log[$-5
1330: 2e 2e 24 5d 3b 0a 09 09 69 6e 74 20 63 6e 74 20 ..$];...int cnt
1340: 3d 20 30 3b 0a 09 09 66 6f 72 65 61 63 68 28 6c = 0;...foreach(l
1350: 3b 20 6c 6f 67 29 0a 09 09 09 69 66 28 6c 5b 30 ; log)....if(l[0
1360: 5d 20 3d 3d 20 6c 6f 67 5b 24 2d 31 5d 5b 30 5d ] == log[$-1][0]
1370: 29 0a 09 09 09 09 2b 2b 63 6e 74 3b 0a 09 09 69 ).....++cnt;...i
1380: 66 28 20 63 6e 74 20 3e 3d 20 33 20 26 26 20 62 f( cnt >= 3 && b
1390: 72 65 61 74 68 3d 3d 31 20 29 20 7b 0a 09 09 09 reath==1 ) {....
13a0: 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 5b 72 forbidden_cell[r
13b0: 6f 2e 79 5d 5b 72 6f 2e 78 5d 20 3d 20 74 72 75 o.y][ro.x] = tru
13c0: 65 3b 0a 09 09 7d 0a 0a 09 09 72 65 74 75 72 6e e;...}....return
13d0: 20 63 3b 0a 09 7d 0a 0a 09 54 75 70 6c 65 21 28 c;..}...Tuple!(
13e0: 63 68 61 72 2c 69 6e 74 29 5b 5d 20 73 65 61 72 char,int)[] sear
13f0: 63 68 28 69 6e 20 47 61 6d 65 20 67 2c 20 69 6e ch(in Game g, in
1400: 20 50 6f 73 20 73 2c 20 69 6e 20 50 6f 73 5b 5d Pos s, in Pos[]
1410: 20 67 73 2c 20 73 74 72 69 6e 67 20 64 65 61 74 gs, string deat
1420: 68 2c 20 62 6f 6f 6c 20 64 61 6e 67 65 72 5f 6f h, bool danger_o
1430: 6b 3d 66 61 6c 73 65 29 0a 09 7b 0a 09 09 62 6f k=false)..{...bo
1440: 6f 6c 20 64 61 6e 67 65 72 28 69 6e 74 20 79 2c ol danger(int y,
1450: 20 69 6e 74 20 78 29 0a 09 09 7b 0a 09 09 09 69 int x)...{....i
1460: 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 20 3d 3d 20 f(g.map[y,x] ==
1470: 27 20 27 20 7c 7c 20 67 2e 6d 61 70 5b 79 2c 78 ' ' || g.map[y,x
1480: 5d 20 3d 3d 20 27 52 27 29 0a 09 09 09 09 72 65 ] == 'R').....re
1490: 74 75 72 6e 20 66 61 6c 73 65 3b 0a 09 09 09 69 turn false;....i
14a0: 66 28 69 73 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 f(is_rocky(g.map
14b0: 5b 79 2b 31 2c 78 5d 29 29 0a 09 09 09 09 72 65 [y+1,x])).....re
14c0: 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 turn true;....if
14d0: 28 69 73 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 5b (is_rocky(g.map[
14e0: 79 2b 31 2c 78 2d 31 5d 29 20 26 26 20 28 67 2e y+1,x-1]) && (g.
14f0: 6d 61 70 5b 79 2c 78 2d 31 5d 3d 3d 27 5c 5c 27 map[y,x-1]=='\\'
1500: 7c 7c 69 73 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 ||is_rocky(g.map
1510: 5b 79 2c 78 2d 31 5d 29 29 0a 09 09 09 20 20 26 [y,x-1])).... &
1520: 26 20 28 67 2e 6d 61 70 5b 79 2b 31 2c 78 5d 3d & (g.map[y+1,x]=
1530: 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2b 31 2c =' '||g.map[y+1,
1540: 78 5d 3d 3d 27 52 27 29 29 0a 09 09 09 09 72 65 x]=='R')).....re
1550: 74 75 72 6e 20 74 72 75 65 3b 0a 09 09 09 69 66 turn true;....if
1560: 28 69 73 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 5b (is_rocky(g.map[
1570: 79 2b 31 2c 78 2b 31 5d 29 20 26 26 20 69 73 5f y+1,x+1]) && is_
1580: 72 6f 63 6b 79 28 67 2e 6d 61 70 5b 79 2c 78 2b rocky(g.map[y,x+
1590: 31 5d 29 20 26 26 20 28 67 2e 6d 61 70 5b 79 2b 1]) && (g.map[y+
15a0: 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 1,x]==' '||g.map
15b0: 5b 79 2b 31 2c 78 5d 3d 3d 27 52 27 29 29 0a 09 [y+1,x]=='R'))..
15c0: 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b 0a ...return true;.
15d0: 09 09 09 69 66 28 69 73 5f 72 6f 63 6b 79 28 67 ...if(is_rocky(g
15e0: 2e 6d 61 70 5b 79 2c 78 2d 31 5d 29 20 26 26 20 .map[y,x-1]) &&
15f0: 28 67 2e 6d 61 70 5b 79 2d 31 2c 78 2d 31 5d 3d (g.map[y-1,x-1]=
1600: 3d 27 5c 5c 27 7c 7c 69 73 5f 72 6f 63 6b 79 28 ='\\'||is_rocky(
1610: 67 2e 6d 61 70 5b 79 2d 31 2c 78 2d 31 5d 29 29 g.map[y-1,x-1]))
1620: 0a 09 09 09 20 20 26 26 20 28 67 2e 6d 61 70 5b .... && (g.map[
1630: 79 2d 31 2c 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d y-1,x]==' '||g.m
1640: 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 52 27 29 29 ap[y-1,x]=='R'))
1650: 0a 09 09 09 09 72 65 74 75 72 6e 20 74 72 75 65 .....return true
1660: 3b 0a 09 09 09 69 66 28 69 73 5f 72 6f 63 6b 79 ;....if(is_rocky
1670: 28 67 2e 6d 61 70 5b 79 2c 78 2b 31 5d 29 20 26 (g.map[y,x+1]) &
1680: 26 20 69 73 5f 72 6f 63 6b 79 28 67 2e 6d 61 70 & is_rocky(g.map
1690: 5b 79 2d 31 2c 78 2b 31 5d 29 20 26 26 20 28 67 [y-1,x+1]) && (g
16a0: 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d 27 20 27 .map[y-1,x]==' '
16b0: 7c 7c 67 2e 6d 61 70 5b 79 2d 31 2c 78 5d 3d 3d ||g.map[y-1,x]==
16c0: 27 52 27 29 29 0a 09 09 09 09 72 65 74 75 72 6e 'R')).....return
16d0: 20 74 72 75 65 3b 0a 09 09 09 72 65 74 75 72 6e true;....return
16e0: 20 66 61 6c 73 65 3b 0a 09 09 7d 0a 0a 09 09 2f false;...}..../
16f0: 2f 20 61 76 6f 69 64 20 64 69 72 65 63 74 6c 79 / avoid directly
1700: 20 62 65 6c 6f 77 20 27 2a 27 0a 09 09 54 75 70 below '*'...Tup
1710: 6c 65 21 28 63 68 61 72 2c 69 6e 74 29 5b 5d 20 le!(char,int)[]
1720: 74 72 79 41 28 29 20 7b 0a 09 09 09 63 6f 6e 73 tryA() {....cons
1730: 74 28 50 6f 73 29 5b 5d 20 71 3b 0a 09 09 09 66 t(Pos)[] q;....f
1740: 6f 72 65 61 63 68 28 70 3b 20 67 73 29 0a 09 09 oreach(p; gs)...
1750: 09 09 69 66 28 21 64 61 6e 67 65 72 28 70 2e 79 ..if(!danger(p.y
1760: 2c 70 2e 78 29 29 0a 09 09 09 09 09 71 20 7e 3d ,p.x))......q ~=
1770: 20 70 3b 0a 09 09 09 62 6f 6f 6c 5b 5d 5b 5d 20 p;....bool[][]
1780: 76 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d v = new bool[][]
1790: 28 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 (g.map.H+2, g.ma
17a0: 70 2e 57 2b 32 29 3b 0a 09 09 09 66 6f 72 65 61 p.W+2);....forea
17b0: 63 68 28 70 3b 20 71 29 20 76 5b 70 2e 79 5d 5b ch(p; q) v[p.y][
17c0: 70 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 09 66 6f p.x]=true;....fo
17d0: 72 28 69 6e 74 20 73 74 65 70 3d 31 3b 20 71 2e r(int step=1; q.
17e0: 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 29 20 length; ++step)
17f0: 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a {.....Pos[] q2;.
1800: 09 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 ....foreach(p; q
1810: 29 20 7b 0a 09 09 09 09 09 69 6e 74 5b 5d 20 79 ) {......int[] y
1820: 79 79 3d 5b 70 2e 79 2d 31 2c 70 2e 79 2b 31 2c yy=[p.y-1,p.y+1,
1830: 70 2e 79 2c 70 2e 79 5d 3b 0a 09 09 09 09 09 69 p.y,p.y];......i
1840: 6e 74 5b 5d 20 78 78 78 3d 5b 70 2e 78 2c 70 2e nt[] xxx=[p.x,p.
1850: 78 2c 70 2e 78 2d 31 2c 70 2e 78 2b 31 5d 3b 0a x,p.x-1,p.x+1];.
1860: 09 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 .....for(int i=0
1870: 3b 20 69 3c 79 79 79 2e 6c 65 6e 67 74 68 3b 20 ; i<yyy.length;
1880: 2b 2b 69 29 20 7b 0a 09 09 09 09 09 09 69 6e 74 ++i) {.......int
1890: 20 79 20 3d 20 79 79 79 5b 69 5d 3b 0a 09 09 09 y = yyy[i];....
18a0: 09 09 09 69 6e 74 20 78 20 3d 20 78 78 78 5b 69 ...int x = xxx[i
18b0: 5d 3b 0a 09 09 09 09 09 09 69 66 28 27 31 27 3c ];.......if('1'<
18c0: 3d 67 2e 6d 61 70 5b 79 2c 78 5d 26 26 67 2e 6d =g.map[y,x]&&g.m
18d0: 61 70 5b 79 2c 78 5d 3c 3d 27 39 27 29 20 7b 0a ap[y,x]<='9') {.
18e0: 09 09 09 09 09 09 09 66 6f 72 65 61 63 68 28 70 .......foreach(p
18f0: 70 70 3b 20 67 2e 74 72 2e 73 6f 75 72 63 65 5f pp; g.tr.source_
1900: 70 6f 73 28 67 2e 6d 61 70 5b 79 2c 78 5d 29 29 pos(g.map[y,x]))
1910: 20 7b 0a 09 09 09 09 09 09 09 09 79 79 79 20 7e {.........yyy ~
1920: 3d 20 70 70 70 2e 79 3b 0a 09 09 09 09 09 09 09 = ppp.y;........
1930: 09 78 78 78 20 7e 3d 20 70 70 70 2e 78 3b 0a 09 .xxx ~= ppp.x;..
1940: 09 09 09 09 09 09 7d 0a 09 09 09 09 09 09 09 63 ......}........c
1950: 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 7d ontinue;.......}
1960: 0a 09 09 09 09 09 09 69 66 28 76 5b 79 5d 5b 78 .......if(v[y][x
1970: 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 ]) continue;....
1980: 09 09 09 69 66 28 79 3d 3d 73 2e 79 20 26 26 20 ...if(y==s.y &&
1990: 78 3d 3d 73 2e 78 20 26 26 20 69 3c 34 29 20 7b x==s.x && i<4) {
19a0: 0a 09 09 09 09 09 09 09 63 68 61 72 20 63 20 3d ........char c =
19b0: 20 22 55 44 52 4c 22 5b 69 5d 3b 0a 09 09 09 09 "UDRL"[i];.....
19c0: 09 09 09 69 66 28 20 64 65 61 74 68 2e 63 6f 75 ...if( death.cou
19d0: 6e 74 28 63 29 20 3d 3d 20 30 20 29 0a 09 09 09 nt(c) == 0 )....
19e0: 09 09 09 09 09 72 65 74 75 72 6e 20 5b 74 75 70 .....return [tup
19f0: 6c 65 28 63 2c 73 74 65 70 29 5d 3b 0a 09 09 09 le(c,step)];....
1a00: 09 09 09 7d 20 65 6c 73 65 20 69 66 28 66 6f 72 ...} else if(for
1a10: 62 69 64 64 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 bidden_cell[y][x
1a20: 5d 29 7b 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 ]){.......} else
1a30: 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d if(g.map[y,x]==
1a40: 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d ' '||g.map[y,x]=
1a50: 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 ='\\'||g.map[y,x
1a60: 5d 3d 3d 27 2e 27 7c 7c 67 2e 6d 61 70 5b 79 2c ]=='.'||g.map[y,
1a70: 78 5d 3d 3d 27 21 27 7c 7c 69 3e 3d 34 29 20 7b x]=='!'||i>=4) {
1a80: 0a 09 09 09 09 09 09 09 69 66 28 64 61 6e 67 65 ........if(dange
1a90: 72 28 79 2c 78 29 29 0a 09 09 09 09 09 09 09 09 r(y,x)).........
1aa0: 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 continue;.......
1ab0: 09 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 .q2 ~= new Pos(y
1ac0: 2c 78 29 3b 0a 09 09 09 09 09 09 09 76 5b 79 5d ,x);........v[y]
1ad0: 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09 09 09 09 [x]=true;.......
1ae0: 7d 0a 09 09 09 09 09 7d 0a 09 09 09 09 7d 0a 09 }......}.....}..
1af0: 09 09 09 71 20 3d 20 71 32 3b 0a 09 09 09 7d 0a ...q = q2;....}.
1b00: 09 09 09 72 65 74 75 72 6e 20 5b 5d 3b 0a 09 09 ...return [];...
1b10: 7d 0a 0a 09 09 2f 2f 20 61 6e 79 20 65 6d 70 74 }....// any empt
1b20: 79 20 73 70 61 63 65 20 69 73 20 6d 79 20 67 72 y space is my gr
1b30: 6f 75 6e 64 0a 09 09 54 75 70 6c 65 21 28 63 68 ound...Tuple!(ch
1b40: 61 72 2c 69 6e 74 29 5b 5d 20 74 72 79 42 28 29 ar,int)[] tryB()
1b50: 20 7b 0a 09 09 09 63 6f 6e 73 74 28 50 6f 73 29 {....const(Pos)
1b60: 5b 5d 20 71 3b 0a 09 09 09 66 6f 72 65 61 63 68 [] q;....foreach
1b70: 28 70 3b 20 67 73 29 20 71 20 7e 3d 20 70 3b 0a (p; gs) q ~= p;.
1b80: 09 09 09 62 6f 6f 6c 5b 5d 5b 5d 20 76 20 3d 20 ...bool[][] v =
1b90: 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d new bool[][](g.m
1ba0: 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b ap.H+2, g.map.W+
1bb0: 32 29 3b 0a 09 09 09 66 6f 72 65 61 63 68 28 70 2);....foreach(p
1bc0: 3b 20 71 29 20 76 5b 70 2e 79 5d 5b 70 2e 78 5d ; q) v[p.y][p.x]
1bd0: 3d 74 72 75 65 3b 0a 09 09 09 66 6f 72 28 69 6e =true;....for(in
1be0: 74 20 73 74 65 70 3d 31 30 3b 20 71 2e 6c 65 6e t step=10; q.len
1bf0: 67 74 68 3b 20 2b 2b 73 74 65 70 29 20 7b 0a 09 gth; ++step) {..
1c00: 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a 09 09 09 ...Pos[] q2;....
1c10: 09 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20 7b .foreach(p; q) {
1c20: 0a 09 09 09 09 09 69 6e 74 5b 5d 20 79 79 79 3d ......int[] yyy=
1c30: 5b 70 2e 79 2d 31 2c 70 2e 79 2b 31 2c 70 2e 79 [p.y-1,p.y+1,p.y
1c40: 2c 70 2e 79 5d 3b 0a 09 09 09 09 09 69 6e 74 5b ,p.y];......int[
1c50: 5d 20 78 78 78 3d 5b 70 2e 78 2c 70 2e 78 2c 70 ] xxx=[p.x,p.x,p
1c60: 2e 78 2d 31 2c 70 2e 78 2b 31 5d 3b 0a 09 09 09 .x-1,p.x+1];....
1c70: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
1c80: 3c 79 79 79 2e 6c 65 6e 67 74 68 3b 20 2b 2b 69 <yyy.length; ++i
1c90: 29 20 7b 0a 09 09 09 09 09 09 69 6e 74 20 79 20 ) {.......int y
1ca0: 3d 20 79 79 79 5b 69 5d 3b 0a 09 09 09 09 09 09 = yyy[i];.......
1cb0: 69 6e 74 20 78 20 3d 20 78 78 78 5b 69 5d 3b 0a int x = xxx[i];.
1cc0: 09 09 09 09 09 09 69 66 28 27 31 27 3c 3d 67 2e ......if('1'<=g.
1cd0: 6d 61 70 5b 79 2c 78 5d 26 26 67 2e 6d 61 70 5b map[y,x]&&g.map[
1ce0: 79 2c 78 5d 3c 3d 27 39 27 29 20 7b 0a 09 09 09 y,x]<='9') {....
1cf0: 09 09 09 09 66 6f 72 65 61 63 68 28 70 70 70 3b ....foreach(ppp;
1d00: 20 67 2e 74 72 2e 73 6f 75 72 63 65 5f 70 6f 73 g.tr.source_pos
1d10: 28 67 2e 6d 61 70 5b 79 2c 78 5d 29 29 20 7b 0a (g.map[y,x])) {.
1d20: 09 09 09 09 09 09 09 09 79 79 79 20 7e 3d 20 70 ........yyy ~= p
1d30: 70 70 2e 79 3b 0a 09 09 09 09 09 09 09 09 78 78 pp.y;.........xx
1d40: 78 20 7e 3d 20 70 70 70 2e 78 3b 0a 09 09 09 09 x ~= ppp.x;.....
1d50: 09 09 09 7d 0a 09 09 09 09 09 09 09 63 6f 6e 74 ...}........cont
1d60: 69 6e 75 65 3b 0a 09 09 09 09 09 09 7d 0a 09 09 inue;.......}...
1d70: 09 09 09 09 69 66 28 76 5b 79 5d 5b 78 5d 29 20 ....if(v[y][x])
1d80: 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 09 continue;.......
1d90: 69 66 28 79 3d 3d 73 2e 79 20 26 26 20 78 3d 3d if(y==s.y && x==
1da0: 73 2e 78 20 26 26 20 69 3c 34 29 20 7b 0a 09 09 s.x && i<4) {...
1db0: 09 09 09 09 09 63 68 61 72 20 63 20 3d 20 22 55 .....char c = "U
1dc0: 44 52 4c 22 5b 69 5d 3b 0a 09 09 09 09 09 09 09 DRL"[i];........
1dd0: 69 66 28 20 64 65 61 74 68 2e 63 6f 75 6e 74 28 if( death.count(
1de0: 63 29 20 3d 3d 20 30 20 29 0a 09 09 09 09 09 09 c) == 0 ).......
1df0: 09 09 72 65 74 75 72 6e 20 5b 74 75 70 6c 65 28 ..return [tuple(
1e00: 63 2c 73 74 65 70 29 5d 3b 0a 09 09 09 09 09 09 c,step)];.......
1e10: 7d 20 65 6c 73 65 20 69 66 28 66 6f 72 62 69 64 } else if(forbid
1e20: 64 65 6e 5f 63 65 6c 6c 5b 79 5d 5b 78 5d 29 7b den_cell[y][x]){
1e30: 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 .......} else if
1e40: 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 (g.map[y,x]==' '
1e50: 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c ||g.map[y,x]=='\
1e60: 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d \'||g.map[y,x]==
1e70: 27 2e 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d '.'||g.map[y,x]=
1e80: 3d 27 21 27 7c 7c 69 3e 3d 34 29 20 7b 0a 09 09 ='!'||i>=4) {...
1e90: 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 50 .....q2 ~= new P
1ea0: 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 09 os(y,x);........
1eb0: 76 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 v[y][x]=true;...
1ec0: 09 09 09 09 7d 0a 09 09 09 09 09 7d 0a 09 09 09 ....}......}....
1ed0: 09 7d 0a 09 09 09 09 71 20 3d 20 71 32 3b 0a 09 .}.....q = q2;..
1ee0: 09 09 7d 0a 09 09 09 72 65 74 75 72 6e 20 5b 5d ..}....return []
1ef0: 3b 0a 09 09 7d 0a 0a 09 09 2f 2f 20 70 75 73 68 ;...}....// push
1f00: 20 72 6f 63 6b 73 21 0a 09 09 54 75 70 6c 65 21 rocks!...Tuple!
1f10: 28 63 68 61 72 2c 69 6e 74 29 5b 5d 20 74 72 79 (char,int)[] try
1f20: 43 28 29 20 7b 0a 09 09 09 63 6f 6e 73 74 28 50 C() {....const(P
1f30: 6f 73 29 5b 5d 20 71 3b 0a 09 09 09 66 6f 72 65 os)[] q;....fore
1f40: 61 63 68 28 70 3b 20 67 73 29 20 71 20 7e 3d 20 ach(p; gs) q ~=
1f50: 70 3b 0a 09 09 09 62 6f 6f 6c 5b 5d 5b 5d 20 76 p;....bool[][] v
1f60: 20 3d 20 6e 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 = new bool[][](
1f70: 67 2e 6d 61 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 g.map.H+2, g.map
1f80: 2e 57 2b 32 29 3b 0a 09 09 09 66 6f 72 65 61 63 .W+2);....foreac
1f90: 68 28 70 3b 20 71 29 20 76 5b 70 2e 79 5d 5b 70 h(p; q) v[p.y][p
1fa0: 2e 78 5d 3d 74 72 75 65 3b 0a 09 09 09 66 6f 72 .x]=true;....for
1fb0: 28 69 6e 74 20 73 74 65 70 3d 32 30 3b 20 71 2e (int step=20; q.
1fc0: 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 29 20 length; ++step)
1fd0: 7b 0a 09 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a {.....Pos[] q2;.
1fe0: 09 09 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 ....foreach(p; q
1ff0: 29 20 7b 0a 09 09 09 09 09 69 6e 74 5b 5d 20 79 ) {......int[] y
2000: 79 79 3d 5b 70 2e 79 2d 31 2c 70 2e 79 2b 31 2c yy=[p.y-1,p.y+1,
2010: 70 2e 79 2c 70 2e 79 5d 3b 0a 09 09 09 09 09 69 p.y,p.y];......i
2020: 6e 74 5b 5d 20 78 78 78 3d 5b 70 2e 78 2c 70 2e nt[] xxx=[p.x,p.
2030: 78 2c 70 2e 78 2d 31 2c 70 2e 78 2b 31 5d 3b 0a x,p.x-1,p.x+1];.
2040: 09 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 .....for(int i=0
2050: 3b 20 69 3c 79 79 79 2e 6c 65 6e 67 74 68 3b 20 ; i<yyy.length;
2060: 2b 2b 69 29 20 7b 0a 09 09 09 09 09 09 69 6e 74 ++i) {.......int
2070: 20 79 20 3d 20 79 79 79 5b 69 5d 3b 0a 09 09 09 y = yyy[i];....
2080: 09 09 09 69 6e 74 20 78 20 3d 20 78 78 78 5b 69 ...int x = xxx[i
2090: 5d 3b 0a 09 09 09 09 09 09 69 66 28 69 73 5f 72 ];.......if(is_r
20a0: 6f 63 6b 79 28 67 2e 6d 61 70 5b 70 5d 29 29 20 ocky(g.map[p]))
20b0: 7b 0a 09 09 09 09 09 09 09 69 66 28 69 3e 3d 34 {........if(i>=4
20c0: 29 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 )continue;......
20d0: 09 09 69 66 28 79 21 3d 70 2e 79 29 63 6f 6e 74 ..if(y!=p.y)cont
20e0: 69 6e 75 65 3b 0a 09 09 09 09 09 09 09 69 66 28 inue;........if(
20f0: 67 2e 6d 61 70 5b 79 2c 70 2e 78 2b 28 70 2e 78 g.map[y,p.x+(p.x
2100: 2d 78 29 5d 21 3d 27 20 27 26 26 67 2e 6d 61 70 -x)]!=' '&&g.map
2110: 5b 79 2c 70 2e 78 2b 28 70 2e 78 2d 78 29 5d 21 [y,p.x+(p.x-x)]!
2120: 3d 27 52 27 29 63 6f 6e 74 69 6e 75 65 3b 0a 09 ='R')continue;..
2130: 09 09 09 09 09 7d 0a 09 09 09 09 09 09 69 66 28 .....}.......if(
2140: 27 31 27 3c 3d 67 2e 6d 61 70 5b 79 2c 78 5d 26 '1'<=g.map[y,x]&
2150: 26 67 2e 6d 61 70 5b 79 2c 78 5d 3c 3d 27 39 27 &g.map[y,x]<='9'
2160: 29 20 7b 0a 09 09 09 09 09 09 09 66 6f 72 65 61 ) {........forea
2170: 63 68 28 70 70 70 3b 20 67 2e 74 72 2e 73 6f 75 ch(ppp; g.tr.sou
2180: 72 63 65 5f 70 6f 73 28 67 2e 6d 61 70 5b 79 2c rce_pos(g.map[y,
2190: 78 5d 29 29 20 7b 0a 09 09 09 09 09 09 09 09 79 x])) {.........y
21a0: 79 79 20 7e 3d 20 70 70 70 2e 79 3b 0a 09 09 09 yy ~= ppp.y;....
21b0: 09 09 09 09 09 78 78 78 20 7e 3d 20 70 70 70 2e .....xxx ~= ppp.
21c0: 78 3b 0a 09 09 09 09 09 09 09 7d 0a 09 09 09 09 x;........}.....
21d0: 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 ...continue;....
21e0: 09 09 09 7d 0a 09 09 09 09 09 09 69 66 28 76 5b ...}.......if(v[
21f0: 79 5d 5b 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b y][x]) continue;
2200: 0a 09 09 09 09 09 09 69 66 28 79 3d 3d 73 2e 79 .......if(y==s.y
2210: 20 26 26 20 78 3d 3d 73 2e 78 20 26 26 20 69 3c && x==s.x && i<
2220: 34 29 20 7b 0a 09 09 09 09 09 09 09 63 68 61 72 4) {........char
2230: 20 63 20 3d 20 22 55 44 52 4c 22 5b 69 5d 3b 0a c = "UDRL"[i];.
2240: 09 09 09 09 09 09 09 69 66 28 20 64 65 61 74 68 .......if( death
2250: 2e 63 6f 75 6e 74 28 63 29 20 3d 3d 20 30 20 29 .count(c) == 0 )
2260: 0a 09 09 09 09 09 09 09 09 72 65 74 75 72 6e 20 .........return
2270: 5b 74 75 70 6c 65 28 63 2c 73 74 65 70 29 5d 3b [tuple(c,step)];
2280: 0a 09 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 .......} else if
2290: 28 66 6f 72 62 69 64 64 65 6e 5f 63 65 6c 6c 5b (forbidden_cell[
22a0: 79 5d 5b 78 5d 29 7b 0a 09 09 09 09 09 09 7d 20 y][x]){.......}
22b0: 65 6c 73 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c else if(g.map[y,
22c0: 78 5d 3d 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 x]==' '||g.map[y
22d0: 2c 78 5d 3d 3d 27 5c 5c 27 7c 7c 67 2e 6d 61 70 ,x]=='\\'||g.map
22e0: 5b 79 2c 78 5d 3d 3d 27 2e 27 7c 7c 69 73 5f 72 [y,x]=='.'||is_r
22f0: 6f 63 6b 79 28 67 2e 6d 61 70 5b 79 2c 78 5d 29 ocky(g.map[y,x])
2300: 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 21 ||g.map[y,x]=='!
2310: 27 7c 7c 69 3e 3d 34 29 20 7b 0a 09 09 09 09 09 '||i>=4) {......
2320: 09 09 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 ..q2 ~= new Pos(
2330: 79 2c 78 29 3b 0a 09 09 09 09 09 09 09 76 5b 79 y,x);........v[y
2340: 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09 09 09 ][x]=true;......
2350: 09 7d 0a 09 09 09 09 09 7d 0a 09 09 09 09 7d 0a .}......}.....}.
2360: 09 09 09 09 71 20 3d 20 71 32 3b 0a 09 09 09 7d ....q = q2;....}
2370: 0a 09 09 09 72 65 74 75 72 6e 20 5b 5d 3b 0a 09 ....return [];..
2380: 09 7d 0a 09 09 72 65 74 75 72 6e 20 28 64 61 6e .}...return (dan
2390: 67 65 72 5f 6f 6b 20 3f 20 5b 5d 20 3a 20 74 72 ger_ok ? [] : tr
23a0: 79 41 28 29 29 20 7e 20 74 72 79 42 28 29 20 7e yA()) ~ tryB() ~
23b0: 20 74 72 79 43 28 29 3b 0a 09 7d 0a 7d 0a 0a 63 tryC();..}.}..c
23c0: 6c 61 73 73 20 e4 be b5 e6 8e a0 e5 a6 82 e7 81 lass ...........
23d0: ab 28 53 75 62 53 6f 6c 76 65 72 29 20 3a 20 53 .(SubSolver) : S
23e0: 6f 6c 76 65 72 0a 7b 0a 09 2f 2f 20 50 61 72 61 olver.{..// Para
23f0: 6d 65 74 65 72 73 2e 0a 09 69 6e 74 20 20 20 20 meters...int
2400: 20 20 20 20 20 20 20 20 50 72 65 64 69 63 74 46 PredictF
2410: 75 74 75 72 65 20 3d 20 31 30 3b 0a 09 63 6f 6e uture = 10;..con
2420: 73 74 20 73 74 72 69 6e 67 5b 5d 20 52 61 6e 64 st string[] Rand
2430: 6f 6d 43 68 6f 69 63 65 50 61 74 74 65 72 6e 3b omChoicePattern;
2440: 20 2f 2f 20 50 46 2a 52 43 50 20 65 78 68 61 75 // PF*RCP exhau
2450: 73 74 69 76 65 20 73 65 61 72 63 68 20 66 6f 72 stive search for
2460: 20 52 4c 20 73 74 65 70 73 0a 09 63 6f 6e 73 74 RL steps..const
2470: 20 20 20 20 20 20 20 20 20 20 52 65 70 6c 61 6e Replan
2480: 4c 65 6e 67 74 68 20 20 3d 20 34 30 30 3b 20 2f Length = 400; /
2490: 2f 20 4f 28 50 46 2a 52 43 50 2a 52 4c 2a 53 75 / O(PF*RCP*RL*Su
24a0: 62 53 6f 6c 76 65 72 2e 73 69 6e 67 6c 65 5f 73 bSolver.single_s
24b0: 74 65 70 29 0a 0a 09 47 61 6d 65 20 20 20 20 20 tep)...Game
24c0: 20 63 75 72 72 65 6e 74 5f 67 61 6d 65 3b 0a 09 current_game;..
24d0: 53 75 62 53 6f 6c 76 65 72 20 73 75 62 5f 73 6f SubSolver sub_so
24e0: 6c 76 65 72 3b 0a 0a 09 65 6e 75 6d 20 7b 54 65 lver;...enum {Te
24f0: 6e 74 61 74 69 76 65 2c 20 54 65 6e 74 61 74 69 ntative, Tentati
2500: 76 65 5f 53 74 75 63 6b 2c 20 46 69 78 65 64 7d ve_Stuck, Fixed}
2510: 3b 0a 09 73 74 72 69 6e 67 20 70 6c 61 6e 3b 0a ;..string plan;.
2520: 09 69 6e 74 20 20 20 20 70 6c 61 6e 5f 73 74 61 .int plan_sta
2530: 74 65 3b 0a 09 69 6e 74 20 20 20 20 72 65 70 6c te;..int repl
2540: 61 6e 5f 6c 69 6d 69 74 3b 0a 09 62 6f 6f 6c 20 an_limit;..bool
2550: 20 20 6c 61 6d 62 64 61 5f 67 65 74 74 65 72 3b lambda_getter;
2560: 0a 09 69 6e 74 20 20 20 20 63 6c 65 61 72 5f 69 ..int clear_i
2570: 6d 70 72 6f 76 65 6d 65 6e 74 20 3d 20 33 3b 0a mprovement = 3;.
2580: 0a 09 74 68 69 73 28 69 6e 20 47 61 6d 65 20 67 ..this(in Game g
2590: 29 0a 09 7b 0a 09 09 63 75 72 72 65 6e 74 5f 67 )..{...current_g
25a0: 61 6d 65 20 3d 20 67 2e 63 6c 6f 6e 65 28 29 3b ame = g.clone();
25b0: 0a 09 09 70 6c 61 6e 20 20 20 20 20 20 20 20 20 ...plan
25c0: 3d 20 22 22 3b 0a 09 09 70 6c 61 6e 5f 73 74 61 = "";...plan_sta
25d0: 74 65 20 20 20 3d 20 54 65 6e 74 61 74 69 76 65 te = Tentative
25e0: 3b 0a 09 09 69 66 28 67 2e 6d 61 70 2e 57 2a 67 ;...if(g.map.W*g
25f0: 2e 6d 61 70 2e 48 20 3c 3d 20 34 30 30 29 20 7b .map.H <= 400) {
2600: 0a 09 09 09 52 61 6e 64 6f 6d 43 68 6f 69 63 65 ....RandomChoice
2610: 50 61 74 74 65 72 6e 20 3d 20 5b 22 55 55 22 2c Pattern = ["UU",
2620: 22 55 44 22 2c 22 55 4c 22 2c 22 55 52 22 2c 0a "UD","UL","UR",.
2630: 09 09 09 20 20 20 20 20 20 20 20 20 20 20 20 20 ...
2640: 20 20 20 20 20 20 20 20 20 20 22 44 55 22 2c 22 "DU","
2650: 44 44 22 2c 22 44 4c 22 2c 22 44 52 22 2c 0a 09 DD","DL","DR",..
2660: 09 09 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ..
2670: 20 20 20 20 20 20 20 20 20 22 4c 55 22 2c 22 4c "LU","L
2680: 44 22 2c 22 4c 4c 22 2c 22 4c 52 22 2c 0a 09 09 D","LL","LR",...
2690: 09 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
26a0: 20 20 20 20 20 20 20 20 22 52 55 22 2c 22 52 44 "RU","RD
26b0: 22 2c 22 52 4c 22 2c 22 52 52 22 2c 22 55 55 55 ","RL","RR","UUU
26c0: 22 2c 22 55 55 55 55 22 2c 22 55 55 55 55 55 22 ","UUUU","UUUUU"
26d0: 5d 3b 0a 09 09 09 50 72 65 64 69 63 74 46 75 74 ];....PredictFut
26e0: 75 72 65 20 3d 20 32 30 3b 0a 09 09 09 63 6c 65 ure = 20;....cle
26f0: 61 72 5f 69 6d 70 72 6f 76 65 6d 65 6e 74 20 3d ar_improvement =
2700: 20 31 3b 0a 09 09 7d 0a 09 09 65 6c 73 65 20 69 1;...}...else i
2710: 66 28 67 2e 6d 61 70 2e 57 2a 67 2e 6d 61 70 2e f(g.map.W*g.map.
2720: 48 20 3c 3d 20 34 30 39 36 29 20 7b 0a 09 09 09 H <= 4096) {....
2730: 52 61 6e 64 6f 6d 43 68 6f 69 63 65 50 61 74 74 RandomChoicePatt
2740: 65 72 6e 20 3d 20 5b 22 55 55 55 22 2c 22 55 22 ern = ["UUU","U"
2750: 2c 22 44 22 2c 22 4c 22 2c 22 52 22 2c 22 55 44 ,"D","L","R","UD
2760: 22 2c 22 44 55 22 2c 22 4c 52 22 2c 22 52 4c 22 ","DU","LR","RL"
2770: 5d 3b 0a 09 09 09 50 72 65 64 69 63 74 46 75 74 ];....PredictFut
2780: 75 72 65 20 3d 20 31 30 3b 0a 09 09 09 63 6c 65 ure = 10;....cle
2790: 61 72 5f 69 6d 70 72 6f 76 65 6d 65 6e 74 20 3d ar_improvement =
27a0: 20 30 3b 0a 09 09 7d 0a 09 09 65 6c 73 65 20 7b 0;...}...else {
27b0: 0a 09 09 09 52 61 6e 64 6f 6d 43 68 6f 69 63 65 ....RandomChoice
27c0: 50 61 74 74 65 72 6e 20 3d 20 5b 22 55 22 2c 22 Pattern = ["U","
27d0: 44 22 2c 22 4c 22 2c 22 52 22 5d 3b 0a 09 09 09 D","L","R"];....
27e0: 50 72 65 64 69 63 74 46 75 74 75 72 65 20 3d 20 PredictFuture =
27f0: 31 30 3b 0a 09 09 09 63 6c 65 61 72 5f 69 6d 70 10;....clear_imp
2800: 72 6f 76 65 6d 65 6e 74 20 3d 20 30 3b 0a 09 09 rovement = 0;...
2810: 7d 0a 0a 09 09 72 65 70 6c 61 6e 5f 6c 69 6d 69 }....replan_limi
2820: 74 20 3d 20 50 72 65 64 69 63 74 46 75 74 75 72 t = PredictFutur
2830: 65 3b 0a 09 7d 0a 0a 09 63 68 61 72 20 73 69 6e e;..}...char sin
2840: 67 6c 65 5f 73 74 65 70 28 29 0a 09 7b 0a 09 09 gle_step()..{...
2850: 69 66 28 63 75 72 72 65 6e 74 5f 67 61 6d 65 2e if(current_game.
2860: 64 65 61 64 20 7c 7c 20 63 75 72 72 65 6e 74 5f dead || current_
2870: 67 61 6d 65 2e 63 6c 65 61 72 65 64 29 0a 09 09 game.cleared)...
2880: 09 72 65 74 75 72 6e 20 27 41 27 3b 0a 0a 09 09 .return 'A';....
2890: 2f 2f 20 4d 61 6b 65 20 65 6e 6f 75 67 68 20 70 // Make enough p
28a0: 72 65 64 69 63 74 69 6f 6e 2e 0a 09 09 77 68 69 rediction....whi
28b0: 6c 65 28 20 70 6c 61 6e 5f 73 74 61 74 65 3d 3d le( plan_state==
28c0: 54 65 6e 74 61 74 69 76 65 20 26 26 20 70 6c 61 Tentative && pla
28d0: 6e 2e 6c 65 6e 67 74 68 3c 72 65 70 6c 61 6e 5f n.length<replan_
28e0: 6c 69 6d 69 74 20 29 0a 09 09 09 73 69 6e 67 6c limit )....singl
28f0: 65 5f 73 74 65 70 5f 70 72 65 64 69 63 74 28 29 e_step_predict()
2900: 3b 0a 0a 09 09 2f 2f 20 49 66 20 74 68 65 20 66 ;....// If the f
2910: 75 74 75 72 65 20 69 73 20 62 61 64 2c 20 63 6f uture is bad, co
2920: 72 72 65 63 74 2e 0a 09 09 69 66 28 20 70 6c 61 rrect....if( pla
2930: 6e 5f 73 74 61 74 65 3d 3d 54 65 6e 74 61 74 69 n_state==Tentati
2940: 76 65 5f 53 74 75 63 6b 20 26 26 20 70 6c 61 6e ve_Stuck && plan
2950: 2e 6c 65 6e 67 74 68 3c 72 65 70 6c 61 6e 5f 6c .length<replan_l
2960: 69 6d 69 74 20 26 26 20 21 6c 61 6d 62 64 61 5f imit && !lambda_
2970: 67 65 74 74 65 72 20 29 0a 09 09 09 72 65 70 6c getter )....repl
2980: 61 6e 28 29 3b 0a 0a 09 09 2f 2f 20 46 6f 6c 6c an();....// Foll
2990: 6f 77 20 74 68 65 20 70 72 65 64 69 63 74 65 64 ow the predicted
29a0: 20 70 6c 61 6e 2e 0a 09 09 69 66 28 20 70 6c 61 plan....if( pla
29b0: 6e 2e 65 6d 70 74 79 20 29 0a 09 09 09 72 65 74 n.empty )....ret
29c0: 75 72 6e 20 27 41 27 3b 0a 09 09 63 68 61 72 20 urn 'A';...char
29d0: 63 20 3d 20 70 6c 61 6e 5b 30 5d 3b 0a 09 09 70 c = plan[0];...p
29e0: 6c 61 6e 20 3d 20 70 6c 61 6e 5b 31 2e 2e 24 5d lan = plan[1..$]
29f0: 3b 0a 09 09 69 6e 74 20 62 5f 6c 61 6d 62 64 61 ;...int b_lambda
2a00: 20 3d 20 63 75 72 72 65 6e 74 5f 67 61 6d 65 2e = current_game.
2a10: 6d 61 70 2e 63 6f 6c 6c 65 63 74 65 64 5f 6c 61 map.collected_la
2a20: 6d 62 64 61 3b 0a 09 09 63 75 72 72 65 6e 74 5f mbda;...current_
2a30: 67 61 6d 65 2e 63 6f 6d 6d 61 6e 64 28 63 29 3b game.command(c);
2a40: 0a 09 09 69 6e 74 20 61 5f 6c 61 6d 62 64 61 20 ...int a_lambda
2a50: 3d 20 63 75 72 72 65 6e 74 5f 67 61 6d 65 2e 6d = current_game.m
2a60: 61 70 2e 63 6f 6c 6c 65 63 74 65 64 5f 6c 61 6d ap.collected_lam
2a70: 62 64 61 3b 0a 09 09 69 66 28 62 5f 6c 61 6d 62 bda;...if(b_lamb
2a80: 64 61 20 3c 20 61 5f 6c 61 6d 62 64 61 29 20 6c da < a_lambda) l
2a90: 61 6d 62 64 61 5f 67 65 74 74 65 72 20 3d 20 66 ambda_getter = f
2aa0: 61 6c 73 65 3b 0a 09 09 72 65 74 75 72 6e 20 63 alse;...return c
2ab0: 3b 0a 09 7d 0a 0a 09 76 6f 69 64 20 66 6f 72 63 ;..}...void forc
2ac0: 65 28 63 68 61 72 20 63 29 0a 09 7b 0a 09 09 69 e(char c)..{...i
2ad0: 66 28 70 6c 61 6e 2e 6c 65 6e 67 74 68 3e 30 20 f(plan.length>0
2ae0: 26 26 20 70 6c 61 6e 5b 30 5d 3d 3d 63 29 0a 09 && plan[0]==c)..
2af0: 09 7b 0a 09 09 09 2f 2f 20 49 66 20 6d 61 74 63 .{....// If matc
2b00: 68 69 6e 67 20 74 68 65 20 70 6c 61 6e 2c 20 6a hing the plan, j
2b10: 75 73 74 20 67 6f 20 66 6f 72 77 61 72 64 2e 0a ust go forward..
2b20: 09 09 09 70 6c 61 6e 20 3d 20 70 6c 61 6e 5b 31 ...plan = plan[1
2b30: 2e 2e 24 5d 3b 0a 09 09 7d 0a 09 09 65 6c 73 65 ..$];...}...else
2b40: 0a 09 09 7b 0a 09 09 09 2f 2f 20 44 69 73 63 61 ...{....// Disca
2b50: 72 64 20 74 68 65 20 70 6c 61 6e 2c 20 6f 74 68 rd the plan, oth
2b60: 65 72 77 69 73 65 2e 0a 09 09 09 70 6c 61 6e 5f erwise.....plan_
2b70: 73 74 61 74 65 20 3d 20 54 65 6e 74 61 74 69 76 state = Tentativ
2b80: 65 3b 0a 09 09 09 70 6c 61 6e 20 20 20 20 20 20 e;....plan
2b90: 20 3d 20 22 22 3b 0a 09 09 09 73 75 62 5f 73 6f = "";....sub_so
2ba0: 6c 76 65 72 20 3d 20 6e 75 6c 6c 3b 0a 09 09 7d lver = null;...}
2bb0: 0a 09 09 63 75 72 72 65 6e 74 5f 67 61 6d 65 2e ...current_game.
2bc0: 63 6f 6d 6d 61 6e 64 28 63 29 3b 0a 09 7d 0a 0a command(c);..}..
2bd0: 09 76 6f 69 64 20 73 69 6e 67 6c 65 5f 73 74 65 .void single_ste
2be0: 70 5f 70 72 65 64 69 63 74 28 29 0a 09 7b 0a 09 p_predict()..{..
2bf0: 09 69 66 28 73 75 62 5f 73 6f 6c 76 65 72 20 69 .if(sub_solver i
2c00: 73 20 6e 75 6c 6c 29 20 7b 0a 09 09 09 73 75 62 s null) {....sub
2c10: 5f 73 6f 6c 76 65 72 20 3d 20 6e 65 77 20 53 75 _solver = new Su
2c20: 62 53 6f 6c 76 65 72 28 63 75 72 72 65 6e 74 5f bSolver(current_
2c30: 67 61 6d 65 29 3b 0a 09 09 09 70 6c 61 6e 20 20 game);....plan
2c40: 20 20 20 20 20 3d 20 22 22 3b 0a 09 09 7d 0a 0a = "";...}..
2c50: 09 09 63 68 61 72 20 63 20 3d 20 73 75 62 5f 73 ..char c = sub_s
2c60: 6f 6c 76 65 72 2e 73 69 6e 67 6c 65 5f 73 74 65 olver.single_ste
2c70: 70 28 29 3b 0a 09 09 69 66 28 63 20 3d 3d 20 27 p();...if(c == '
2c80: 41 27 29 0a 09 09 09 70 6c 61 6e 5f 73 74 61 74 A')....plan_stat
2c90: 65 20 3d 20 54 65 6e 74 61 74 69 76 65 5f 53 74 e = Tentative_St
2ca0: 75 63 6b 3b 0a 09 09 65 6c 73 65 20 7b 0a 09 09 uck;...else {...
2cb0: 09 70 6c 61 6e 20 7e 3d 20 63 3b 0a 09 09 09 69 .plan ~= c;....i
2cc0: 66 28 73 75 62 5f 73 6f 6c 76 65 72 2e 67 2e 63 f(sub_solver.g.c
2cd0: 6c 65 61 72 65 64 29 20 7b 0a 09 09 09 09 69 66 leared) {.....if
2ce0: 28 63 6c 65 61 72 5f 69 6d 70 72 6f 76 65 6d 65 (clear_improveme
2cf0: 6e 74 2d 2d 3e 30 29 20 7b 0a 09 09 09 09 09 70 nt-->0) {......p
2d00: 6c 61 6e 5f 73 74 61 74 65 20 3d 20 54 65 6e 74 lan_state = Tent
2d10: 61 74 69 76 65 5f 53 74 75 63 6b 3b 0a 09 09 09 ative_Stuck;....
2d20: 09 09 72 65 70 6c 61 6e 5f 6c 69 6d 69 74 20 3d ..replan_limit =
2d30: 20 6d 69 6e 28 70 6c 61 6e 2e 6c 65 6e 67 74 68 min(plan.length
2d40: 2d 70 6c 61 6e 2e 6c 65 6e 67 74 68 2f 28 63 6c -plan.length/(cl
2d50: 65 61 72 5f 69 6d 70 72 6f 76 65 6d 65 6e 74 2b ear_improvement+
2d60: 31 29 2c 20 50 72 65 64 69 63 74 46 75 74 75 72 1), PredictFutur
2d70: 65 29 3b 0a 09 09 09 09 7d 20 65 6c 73 65 20 7b e);.....} else {
2d80: 0a 09 09 09 09 09 70 6c 61 6e 5f 73 74 61 74 65 ......plan_state
2d90: 20 3d 20 46 69 78 65 64 3b 0a 09 09 09 09 7d 0a = Fixed;.....}.
2da0: 09 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 09 09 ...} else {.....
2db0: 70 6c 61 6e 5f 73 74 61 74 65 20 3d 20 28 73 75 plan_state = (su
2dc0: 62 5f 73 6f 6c 76 65 72 2e 67 2e 64 65 61 64 20 b_solver.g.dead
2dd0: 3f 20 54 65 6e 74 61 74 69 76 65 5f 53 74 75 63 ? Tentative_Stuc
2de0: 6b 20 3a 20 54 65 6e 74 61 74 69 76 65 29 3b 0a k : Tentative);.
2df0: 09 09 09 7d 0a 09 09 7d 0a 09 7d 0a 0a 09 76 6f ...}...}..}...vo
2e00: 69 64 20 72 65 70 6c 61 6e 28 29 0a 09 7b 0a 09 id replan()..{..
2e10: 09 2f 2f 20 54 72 79 20 74 6f 20 72 65 70 6c 61 .// Try to repla
2e20: 63 65 20 65 76 65 72 79 20 73 74 65 70 20 6f 66 ce every step of
2e30: 20 74 68 65 20 70 6c 61 6e 20 62 79 20 61 6e 6f the plan by ano
2e40: 74 68 65 72 20 6d 6f 76 65 2e 0a 09 09 47 61 6d ther move....Gam
2e50: 65 20 67 20 3d 20 63 75 72 72 65 6e 74 5f 67 61 e g = current_ga
2e60: 6d 65 2e 63 6c 6f 6e 65 28 29 3b 0a 09 09 54 75 me.clone();...Tu
2e70: 70 6c 65 21 28 53 75 62 53 6f 6c 76 65 72 2c 20 ple!(SubSolver,
2e80: 73 74 72 69 6e 67 2c 20 69 6e 74 29 20 63 61 6e string, int) can
2e90: 64 20 3d 20 74 75 70 6c 65 28 73 75 62 5f 73 6f d = tuple(sub_so
2ea0: 6c 76 65 72 2c 20 70 6c 61 6e 2c 20 54 65 6e 74 lver, plan, Tent
2eb0: 61 74 69 76 65 5f 53 74 75 63 6b 29 3b 0a 09 09 ative_Stuck);...
2ec0: 69 6e 74 20 69 6e 73 65 72 74 69 6f 6e 5f 70 6f int insertion_po
2ed0: 69 6e 74 20 3d 20 70 6c 61 6e 2e 6c 65 6e 67 74 int = plan.lengt
2ee0: 68 3b 0a 09 09 62 6f 6f 6c 20 74 69 65 62 72 65 h;...bool tiebre
2ef0: 61 6b 5f 62 79 5f 74 75 72 6e 20 3d 20 66 61 6c ak_by_turn = fal
2f00: 73 65 3b 0a 09 09 69 6e 74 20 63 6f 6e 73 69 64 se;...int consid
2f10: 65 72 5f 6c 65 6e 67 74 68 20 3d 20 6d 69 6e 28 er_length = min(
2f20: 52 65 70 6c 61 6e 4c 65 6e 67 74 68 2c 20 67 2e ReplanLength, g.
2f30: 6d 61 70 2e 57 2a 67 2e 6d 61 70 2e 48 29 3b 0a map.W*g.map.H);.
2f40: 09 09 69 66 28 63 61 6e 64 5b 30 5d 2e 67 2e 63 ..if(cand[0].g.c
2f50: 6c 65 61 72 65 64 29 20 63 6f 6e 73 69 64 65 72 leared) consider
2f60: 5f 6c 65 6e 67 74 68 20 3d 20 6d 69 6e 28 63 6f _length = min(co
2f70: 6e 73 69 64 65 72 5f 6c 65 6e 67 74 68 2c 20 63 nsider_length, c
2f80: 61 6e 64 5b 31 5d 2e 6c 65 6e 67 74 68 29 3b 0a and[1].length);.
2f90: 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
2fa0: 69 3c 70 6c 61 6e 2e 6c 65 6e 67 74 68 3b 20 2b i<plan.length; +
2fb0: 2b 69 29 20 7b 0a 09 09 09 66 6f 72 65 61 63 68 +i) {....foreach
2fc0: 28 73 74 72 69 6e 67 20 70 72 65 66 69 78 3b 20 (string prefix;
2fd0: 52 61 6e 64 6f 6d 43 68 6f 69 63 65 50 61 74 74 RandomChoicePatt
2fe0: 65 72 6e 29 0a 09 09 09 09 69 66 28 70 72 65 66 ern).....if(pref
2ff0: 69 78 5b 30 5d 20 21 3d 20 70 6c 61 6e 5b 69 5d ix[0] != plan[i]
3000: 29 20 7b 0a 09 09 09 09 09 54 75 70 6c 65 21 28 ) {......Tuple!(
3010: 53 75 62 53 6f 6c 76 65 72 2c 20 73 74 72 69 6e SubSolver, strin
3020: 67 2c 20 69 6e 74 29 20 72 20 3d 20 74 72 79 5f g, int) r = try_
3030: 70 6c 61 6e 28 67 2c 20 70 72 65 66 69 78 2c 20 plan(g, prefix,
3040: 63 6f 6e 73 69 64 65 72 5f 6c 65 6e 67 74 68 2d consider_length-
3050: 69 2d 70 72 65 66 69 78 2e 6c 65 6e 67 74 68 29 i-prefix.length)
3060: 3b 0a 09 09 09 09 09 72 5b 31 5d 20 3d 20 70 6c ;......r[1] = pl
3070: 61 6e 5b 30 2e 2e 69 5d 20 7e 20 70 72 65 66 69 an[0..i] ~ prefi
3080: 78 20 7e 20 72 5b 31 5d 3b 0a 09 09 09 09 09 62 x ~ r[1];......b
3090: 6f 6f 6c 20 62 65 74 74 65 72 20 3d 20 66 61 6c ool better = fal
30a0: 73 65 2c 20 74 62 74 3d 66 61 6c 73 65 3b 0a 09 se, tbt=false;..
30b0: 09 09 09 09 69 66 28 21 63 61 6e 64 5b 30 5d 2e ....if(!cand[0].
30c0: 67 2e 63 6c 65 61 72 65 64 20 26 26 20 72 5b 30 g.cleared && r[0
30d0: 5d 2e 67 2e 63 6c 65 61 72 65 64 29 0a 09 09 09 ].g.cleared)....
30e0: 09 09 09 62 65 74 74 65 72 20 3d 20 74 72 75 65 ...better = true
30f0: 3b 0a 09 09 09 09 09 65 6c 73 65 20 69 66 28 63 ;......else if(c
3100: 61 6e 64 5b 30 5d 2e 67 2e 63 6c 65 61 72 65 64 and[0].g.cleared
3110: 20 26 26 20 72 5b 30 5d 2e 67 2e 63 6c 65 61 72 && r[0].g.clear
3120: 65 64 29 20 7b 0a 09 09 09 09 09 09 62 65 74 74 ed) {.......bett
3130: 65 72 20 3d 20 63 61 6e 64 5b 30 5d 2e 67 2e 73 er = cand[0].g.s
3140: 63 6f 72 65 20 3c 20 72 5b 30 5d 2e 67 2e 73 63 core < r[0].g.sc
3150: 6f 72 65 3b 0a 09 09 09 09 09 7d 0a 09 09 09 09 ore;......}.....
3160: 09 65 6c 73 65 20 69 66 28 21 63 61 6e 64 5b 30 .else if(!cand[0
3170: 5d 2e 67 2e 63 6c 65 61 72 65 64 20 26 26 20 21 ].g.cleared && !
3180: 72 5b 30 5d 2e 67 2e 63 6c 65 61 72 65 64 29 20 r[0].g.cleared)
3190: 7b 0a 09 09 09 09 09 09 69 66 28 63 61 6e 64 5b {.......if(cand[
31a0: 30 5d 2e 67 2e 6d 61 70 2e 63 6f 6c 6c 65 63 74 0].g.map.collect
31b0: 65 64 5f 6c 61 6d 62 64 61 20 3c 20 72 5b 30 5d ed_lambda < r[0]
31c0: 2e 67 2e 6d 61 70 2e 63 6f 6c 6c 65 63 74 65 64 .g.map.collected
31d0: 5f 6c 61 6d 62 64 61 29 0a 09 09 09 09 09 09 09 _lambda)........
31e0: 62 65 74 74 65 72 20 3d 20 74 72 75 65 3b 0a 09 better = true;..
31f0: 09 09 09 09 09 65 6c 73 65 20 69 66 28 63 61 6e .....else if(can
3200: 64 5b 30 5d 2e 67 2e 6d 61 70 2e 63 6f 6c 6c 65 d[0].g.map.colle
3210: 63 74 65 64 5f 6c 61 6d 62 64 61 20 3d 3d 20 72 cted_lambda == r
3220: 5b 30 5d 2e 67 2e 6d 61 70 2e 63 6f 6c 6c 65 63 [0].g.map.collec
3230: 74 65 64 5f 6c 61 6d 62 64 61 29 20 7b 0a 09 09 ted_lambda) {...
3240: 09 09 09 09 09 69 66 28 63 61 6e 64 5b 30 5d 2e .....if(cand[0].
3250: 67 2e 64 65 61 64 20 26 26 20 21 72 5b 30 5d 2e g.dead && !r[0].
3260: 67 2e 64 65 61 64 29 0a 09 09 09 09 09 09 09 09 g.dead).........
3270: 62 65 74 74 65 72 20 3d 20 74 72 75 65 3b 0a 09 better = true;..
3280: 09 09 09 09 09 09 65 6c 73 65 20 69 66 28 63 61 ......else if(ca
3290: 6e 64 5b 30 5d 2e 67 2e 64 65 61 64 20 3d 3d 20 nd[0].g.dead ==
32a0: 72 5b 30 5d 2e 67 2e 64 65 61 64 29 20 7b 0a 09 r[0].g.dead) {..
32b0: 09 09 09 09 09 09 09 62 65 74 74 65 72 20 3d 20 .......better =
32c0: 28 63 61 6e 64 5b 31 5d 2e 6c 65 6e 67 74 68 20 (cand[1].length
32d0: 3c 20 72 5b 31 5d 2e 6c 65 6e 67 74 68 20 26 26 < r[1].length &&
32e0: 20 72 5b 32 5d 21 3d 54 65 6e 74 61 74 69 76 65 r[2]!=Tentative
32f0: 5f 53 74 75 63 6b 29 3b 0a 09 09 09 09 09 09 09 _Stuck);........
3300: 09 74 62 74 20 3d 20 74 72 75 65 3b 0a 09 09 09 .tbt = true;....
3310: 09 09 09 09 7d 0a 09 09 09 09 09 09 7d 0a 09 09 ....}.......}...
3320: 09 09 09 7d 0a 09 09 09 09 09 69 66 28 62 65 74 ...}......if(bet
3330: 74 65 72 29 20 7b 0a 09 09 09 09 09 09 63 61 6e ter) {.......can
3340: 64 20 3d 20 72 3b 0a 09 09 09 09 09 09 74 69 65 d = r;.......tie
3350: 62 72 65 61 6b 5f 62 79 5f 74 75 72 6e 20 3d 20 break_by_turn =
3360: 74 72 75 65 3b 0a 09 09 09 09 09 09 69 6e 73 65 true;.......inse
3370: 72 74 69 6f 6e 5f 70 6f 69 6e 74 20 3d 20 69 2b rtion_point = i+
3380: 70 72 65 66 69 78 2e 6c 65 6e 67 74 68 3b 0a 09 prefix.length;..
3390: 09 09 09 09 09 69 66 28 72 5b 30 5d 2e 67 2e 63 .....if(r[0].g.c
33a0: 6c 65 61 72 65 64 29 20 63 6f 6e 73 69 64 65 72 leared) consider
33b0: 5f 6c 65 6e 67 74 68 20 3d 20 6d 69 6e 28 63 6f _length = min(co
33c0: 6e 73 69 64 65 72 5f 6c 65 6e 67 74 68 2c 20 72 nsider_length, r
33d0: 5b 31 5d 2e 6c 65 6e 67 74 68 29 3b 0a 09 09 09 [1].length);....
33e0: 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 67 2e 63 ..}.....}....g.c
33f0: 6f 6d 6d 61 6e 64 28 70 6c 61 6e 5b 69 5d 29 3b ommand(plan[i]);
3400: 0a 09 09 7d 0a 0a 09 09 69 66 28 63 61 6e 64 5b ...}....if(cand[
3410: 32 5d 3d 3d 46 69 78 65 64 20 26 26 20 69 6e 73 2]==Fixed && ins
3420: 65 72 74 69 6f 6e 5f 70 6f 69 6e 74 21 3d 70 6c ertion_point!=pl
3430: 61 6e 2e 6c 65 6e 67 74 68 20 26 26 20 63 6c 65 an.length && cle
3440: 61 72 5f 69 6d 70 72 6f 76 65 6d 65 6e 74 2d 2d ar_improvement--
3450: 3e 30 29 20 7b 0a 09 09 09 73 75 62 5f 73 6f 6c >0) {....sub_sol
3460: 76 65 72 20 20 20 3d 20 63 61 6e 64 5b 30 5d 3b ver = cand[0];
3470: 0a 09 09 09 70 6c 61 6e 20 20 20 20 20 20 20 20 ....plan
3480: 20 3d 20 63 61 6e 64 5b 31 5d 3b 0a 09 09 09 70 = cand[1];....p
3490: 6c 61 6e 5f 73 74 61 74 65 20 20 20 3d 20 54 65 lan_state = Te
34a0: 6e 74 61 74 69 76 65 5f 53 74 75 63 6b 3b 0a 09 ntative_Stuck;..
34b0: 09 09 72 65 70 6c 61 6e 5f 6c 69 6d 69 74 20 3d ..replan_limit =
34c0: 20 6d 69 6e 28 70 6c 61 6e 2e 6c 65 6e 67 74 68 min(plan.length
34d0: 20 2d 20 69 6e 73 65 72 74 69 6f 6e 5f 70 6f 69 - insertion_poi
34e0: 6e 74 2c 20 50 72 65 64 69 63 74 46 75 74 75 72 nt, PredictFutur
34f0: 65 29 3b 0a 09 09 09 6c 61 6d 62 64 61 5f 67 65 e);....lambda_ge
3500: 74 74 65 72 20 3d 20 63 75 72 72 65 6e 74 5f 67 tter = current_g
3510: 61 6d 65 2e 6d 61 70 2e 63 6f 6c 6c 65 63 74 65 ame.map.collecte
3520: 64 5f 6c 61 6d 62 64 61 20 3c 20 63 61 6e 64 5b d_lambda < cand[
3530: 30 5d 2e 67 2e 6d 61 70 2e 63 6f 6c 6c 65 63 74 0].g.map.collect
3540: 65 64 5f 6c 61 6d 62 64 61 3b 0a 09 09 7d 20 65 ed_lambda;...} e
3550: 6c 73 65 20 7b 0a 09 09 09 73 75 62 5f 73 6f 6c lse {....sub_sol
3560: 76 65 72 20 20 20 3d 20 63 61 6e 64 5b 30 5d 3b ver = cand[0];
3570: 0a 09 09 09 70 6c 61 6e 20 20 20 20 20 20 20 20 ....plan
3580: 20 3d 20 63 61 6e 64 5b 31 5d 3b 0a 09 09 09 70 = cand[1];....p
3590: 6c 61 6e 5f 73 74 61 74 65 20 20 20 3d 20 28 70 lan_state = (p
35a0: 6c 61 6e 2e 6c 65 6e 67 74 68 20 3c 20 50 72 65 lan.length < Pre
35b0: 64 69 63 74 46 75 74 75 72 65 20 3f 20 46 69 78 dictFuture ? Fix
35c0: 65 64 20 3a 20 63 61 6e 64 5b 32 5d 29 3b 0a 09 ed : cand[2]);..
35d0: 09 09 72 65 70 6c 61 6e 5f 6c 69 6d 69 74 20 3d ..replan_limit =
35e0: 20 74 69 65 62 72 65 61 6b 5f 62 79 5f 74 75 72 tiebreak_by_tur
35f0: 6e 20 3f 20 6d 69 6e 28 50 72 65 64 69 63 74 46 n ? min(PredictF
3600: 75 74 75 72 65 2c 20 28 70 6c 61 6e 2e 6c 65 6e uture, (plan.len
3610: 67 74 68 2b 31 29 2f 32 29 20 3a 20 50 72 65 64 gth+1)/2) : Pred
3620: 69 63 74 46 75 74 75 72 65 3b 0a 09 09 09 6c 61 ictFuture;....la
3630: 6d 62 64 61 5f 67 65 74 74 65 72 20 3d 20 63 75 mbda_getter = cu
3640: 72 72 65 6e 74 5f 67 61 6d 65 2e 6d 61 70 2e 63 rrent_game.map.c
3650: 6f 6c 6c 65 63 74 65 64 5f 6c 61 6d 62 64 61 20 ollected_lambda
3660: 3c 20 63 61 6e 64 5b 30 5d 2e 67 2e 6d 61 70 2e < cand[0].g.map.
3670: 63 6f 6c 6c 65 63 74 65 64 5f 6c 61 6d 62 64 61 collected_lambda
3680: 3b 0a 09 09 7d 0a 09 7d 0a 0a 09 54 75 70 6c 65 ;...}..}...Tuple
3690: 21 28 53 75 62 53 6f 6c 76 65 72 2c 20 73 74 72 !(SubSolver, str
36a0: 69 6e 67 2c 20 69 6e 74 29 20 74 72 79 5f 70 6c ing, int) try_pl
36b0: 61 6e 28 69 6e 20 47 61 6d 65 20 67 2c 20 73 74 an(in Game g, st
36c0: 72 69 6e 67 20 70 72 65 66 69 78 2c 20 69 6e 74 ring prefix, int
36d0: 20 63 6f 6e 73 69 64 65 72 5f 6c 65 6e 67 74 68 consider_length
36e0: 29 0a 09 7b 0a 09 09 69 66 28 63 6f 6e 73 69 64 )..{...if(consid
36f0: 65 72 5f 6c 65 6e 67 74 68 3c 3d 30 29 20 63 6f er_length<=0) co
3700: 6e 73 69 64 65 72 5f 6c 65 6e 67 74 68 20 3d 20 nsider_length =
3710: 32 3b 0a 0a 09 09 53 75 62 53 6f 6c 76 65 72 20 2;....SubSolver
3720: 73 20 3d 20 6e 65 77 20 53 75 62 53 6f 6c 76 65 s = new SubSolve
3730: 72 28 67 29 3b 0a 09 09 66 6f 72 65 61 63 68 28 r(g);...foreach(
3740: 63 68 61 72 20 63 3b 20 70 72 65 66 69 78 29 0a char c; prefix).
3750: 09 09 09 73 2e 66 6f 72 63 65 28 63 29 3b 0a 09 ...s.force(c);..
3760: 09 73 74 72 69 6e 67 20 6c 6f 67 3b 0a 09 09 69 .string log;...i
3770: 6e 74 20 73 74 61 74 65 20 3d 20 54 65 6e 74 61 nt state = Tenta
3780: 74 69 76 65 3b 0a 09 09 77 68 69 6c 65 28 21 73 tive;...while(!s
3790: 2e 67 2e 63 6c 65 61 72 65 64 20 26 26 20 21 73 .g.cleared && !s
37a0: 2e 67 2e 64 65 61 64 20 26 26 20 6c 6f 67 2e 6c .g.dead && log.l
37b0: 65 6e 67 74 68 3c 3d 63 6f 6e 73 69 64 65 72 5f ength<=consider_
37c0: 6c 65 6e 67 74 68 29 20 7b 0a 09 09 09 63 68 61 length) {....cha
37d0: 72 20 63 20 3d 20 73 2e 73 69 6e 67 6c 65 5f 73 r c = s.single_s
37e0: 74 65 70 28 29 3b 0a 09 09 09 69 66 28 20 63 20 tep();....if( c
37f0: 3d 3d 20 27 41 27 20 29 20 7b 0a 09 09 09 09 73 == 'A' ) {.....s
3800: 74 61 74 65 20 3d 20 54 65 6e 74 61 74 69 76 65 tate = Tentative
3810: 5f 53 74 75 63 6b 3b 0a 09 09 09 09 62 72 65 61 _Stuck;.....brea
3820: 6b 3b 0a 09 09 09 7d 0a 09 09 09 6c 6f 67 20 7e k;....}....log ~
3830: 3d 20 63 3b 0a 09 09 7d 0a 09 09 69 66 28 73 2e = c;...}...if(s.
3840: 67 2e 63 6c 65 61 72 65 64 29 20 73 74 61 74 65 g.cleared) state
3850: 20 3d 20 46 69 78 65 64 3b 0a 09 09 65 6c 73 65 = Fixed;...else
3860: 20 69 66 28 73 2e 67 2e 64 65 61 64 29 20 73 74 if(s.g.dead) st
3870: 61 74 65 20 3d 20 54 65 6e 74 61 74 69 76 65 5f ate = Tentative_
3880: 53 74 75 63 6b 3b 0a 09 09 72 65 74 75 72 6e 20 Stuck;...return
3890: 74 75 70 6c 65 28 73 2c 20 6c 6f 67 2c 20 73 74 tuple(s, log, st
38a0: 61 74 65 29 3b 0a 09 7d 0a 7d 0a 0a 63 6c 61 73 ate);..}.}..clas
38b0: 73 20 51 75 65 75 65 28 54 29 0a 7b 0a 09 61 6c s Queue(T).{..al
38c0: 69 61 73 20 54 75 70 6c 65 21 28 54 2c 69 6e 74 ias Tuple!(T,int
38d0: 29 20 74 3b 0a 0a 09 74 5b 5d 20 63 75 72 2c 20 ) t;...t[] cur,
38e0: 6e 65 78 74 3b 0a 0a 09 76 6f 69 64 20 70 75 73 next;...void pus
38f0: 68 28 54 20 76 2c 20 69 6e 74 20 70 29 20 7b 20 h(T v, int p) {
3900: 28 63 75 72 2e 65 6d 70 74 79 20 3f 20 63 75 72 (cur.empty ? cur
3910: 20 3a 20 6e 65 78 74 29 20 7e 3d 20 74 75 70 6c : next) ~= tupl
3920: 65 28 76 2c 70 29 3b 20 7d 0a 09 62 6f 6f 6c 20 e(v,p); }..bool
3930: 65 6d 70 74 79 28 29 20 7b 20 72 65 74 75 72 6e empty() { return
3940: 20 63 75 72 2e 65 6d 70 74 79 3b 20 7d 0a 09 74 cur.empty; }..t
3950: 20 70 6f 70 28 29 20 7b 0a 09 09 74 20 76 20 3d pop() {...t v =
3960: 20 63 75 72 5b 30 5d 3b 20 63 75 72 20 3d 20 63 cur[0]; cur = c
3970: 75 72 5b 31 2e 2e 24 5d 3b 0a 09 09 69 66 28 63 ur[1..$];...if(c
3980: 75 72 2e 65 6d 70 74 79 29 20 7b 20 63 75 72 20 ur.empty) { cur
3990: 3d 20 6e 65 78 74 3b 20 6e 65 78 74 20 3d 20 6e = next; next = n
39a0: 75 6c 6c 3b 20 7d 0a 09 09 72 65 74 75 72 6e 20 ull; }...return
39b0: 76 3b 0a 09 7d 0a 7d 0a 0a 63 6c 61 73 73 20 e7 v;..}.}..class .
39c0: 96 be e5 a6 82 e9 a2 a8 20 3a 20 53 6f 6c 76 65 ........ : Solve
39d0: 72 0a 7b 0a 09 47 61 6d 65 20 67 3b 0a 09 74 68 r.{..Game g;..th
39e0: 69 73 28 69 6e 20 47 61 6d 65 20 67 29 0a 09 7b is(in Game g)..{
39f0: 0a 09 09 74 68 69 73 2e 67 20 3d 20 67 2e 63 6c ...this.g = g.cl
3a00: 6f 6e 65 28 29 3b 0a 09 7d 0a 0a 09 63 68 61 72 one();..}...char
3a10: 20 73 69 6e 67 6c 65 5f 73 74 65 70 28 29 0a 09 single_step()..
3a20: 7b 0a 09 09 61 75 74 6f 20 64 6d 20 3d 20 64 65 {...auto dm = de
3a30: 61 74 68 5f 6d 6f 76 65 28 67 29 3b 0a 0a 09 09 ath_move(g);....
3a40: 63 68 61 72 20 63 20 3d 20 74 68 69 6e 6b 28 67 char c = think(g
3a50: 2c 20 64 6d 5b 30 5d 29 3b 0a 09 09 69 66 28 63 , dm[0]);...if(c
3a60: 20 3d 3d 20 27 57 27 29 20 7b 0a 09 09 09 77 61 == 'W') {....wa
3a70: 69 74 5f 63 6f 75 6e 74 65 72 2b 2b 3b 0a 09 09 it_counter++;...
3a80: 09 69 66 28 64 6d 5b 30 5d 2e 63 6f 75 6e 74 28 .if(dm[0].count(
3a90: 63 29 20 7c 7c 20 77 61 69 74 5f 63 6f 75 6e 74 c) || wait_count
3aa0: 65 72 3e 3d 33 29 20 7b 0a 09 09 09 09 63 20 3d er>=3) {.....c =
3ab0: 20 27 41 27 3b 0a 09 09 09 09 66 6f 72 65 61 63 'A';.....foreac
3ac0: 68 28 63 68 61 72 20 63 63 3b 20 22 44 4c 52 55 h(char cc; "DLRU
3ad0: 22 29 0a 09 09 09 09 09 69 66 28 64 6d 5b 30 5d ")......if(dm[0]
3ae0: 2e 63 6f 75 6e 74 28 63 63 29 20 3d 3d 20 30 29 .count(cc) == 0)
3af0: 0a 09 09 09 09 09 09 63 20 3d 20 63 63 3b 0a 09 .......c = cc;..
3b00: 09 09 7d 0a 09 09 09 69 66 28 77 61 69 74 5f 63 ..}....if(wait_c
3b10: 6f 75 6e 74 65 72 20 3e 20 32 30 29 0a 09 09 09 ounter > 20)....
3b20: 09 63 20 3d 20 27 41 27 3b 0a 09 09 7d 20 65 6c .c = 'A';...} el
3b30: 73 65 20 7b 0a 09 09 09 77 61 69 74 5f 63 6f 75 se {....wait_cou
3b40: 6e 74 65 72 20 3d 20 30 3b 0a 09 09 7d 0a 09 09 nter = 0;...}...
3b50: 69 66 28 63 20 21 3d 20 27 41 27 29 0a 09 09 09 if(c != 'A')....
3b60: 67 2e 63 6f 6d 6d 61 6e 64 28 63 29 3b 0a 09 09 g.command(c);...
3b70: 72 65 74 75 72 6e 20 63 3b 0a 09 7d 0a 0a 09 76 return c;..}...v
3b80: 6f 69 64 20 66 6f 72 63 65 28 63 68 61 72 20 63 oid force(char c
3b90: 29 0a 09 7b 0a 09 09 69 66 28 63 20 21 3d 20 27 )..{...if(c != '
3ba0: 41 27 29 0a 09 09 09 67 2e 63 6f 6d 6d 61 6e 64 A')....g.command
3bb0: 28 63 29 3b 0a 09 7d 0a 0a 09 69 6e 74 20 77 61 (c);..}...int wa
3bc0: 69 74 5f 63 6f 75 6e 74 65 72 20 3d 20 30 3b 0a it_counter = 0;.
3bd0: 0a 09 63 68 61 72 20 74 68 69 6e 6b 28 69 6e 20 ..char think(in
3be0: 47 61 6d 65 20 67 2c 20 73 74 72 69 6e 67 20 64 Game g, string d
3bf0: 65 61 74 68 29 0a 09 7b 0a 09 09 61 75 74 6f 20 eath)..{...auto
3c00: 51 20 3d 20 6e 65 77 20 51 75 65 75 65 21 28 54 Q = new Queue!(T
3c10: 75 70 6c 65 21 28 50 6f 73 2c 50 6f 73 29 29 3b uple!(Pos,Pos));
3c20: 0a 09 09 51 2e 70 75 73 68 28 74 75 70 6c 65 28 ...Q.push(tuple(
3c30: 67 2e 6d 61 70 2e 72 6f 62 6f 74 2e 63 6c 6f 6e g.map.robot.clon
3c40: 65 28 29 2c 20 67 2e 6d 61 70 2e 72 6f 62 6f 74 e(), g.map.robot
3c50: 2e 63 6c 6f 6e 65 28 29 29 2c 20 30 29 3b 0a 09 .clone()), 0);..
3c60: 09 50 6f 73 5b 5d 5b 5d 20 56 20 3d 20 6e 65 77 .Pos[][] V = new
3c70: 20 50 6f 73 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 Pos[][](g.map.H
3c80: 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a +2, g.map.W+2);.
3c90: 09 09 77 68 69 6c 65 28 21 51 2e 65 6d 70 74 79 ..while(!Q.empty
3ca0: 29 20 7b 0a 09 09 09 61 75 74 6f 20 74 75 70 20 ) {....auto tup
3cb0: 3d 20 51 2e 70 6f 70 28 29 3b 0a 09 09 09 50 6f = Q.pop();....Po
3cc0: 73 20 20 70 20 20 20 20 3d 20 74 75 70 5b 30 5d s p = tup[0]
3cd0: 5b 30 5d 3b 0a 09 09 09 50 6f 73 20 20 70 72 65 [0];....Pos pre
3ce0: 76 20 3d 20 74 75 70 5b 30 5d 5b 31 5d 3b 0a 09 v = tup[0][1];..
3cf0: 09 09 69 6e 74 20 20 64 69 73 74 20 3d 20 74 75 ..int dist = tu
3d00: 70 5b 31 5d 3b 0a 09 09 09 69 66 28 56 5b 70 2e p[1];....if(V[p.
3d10: 79 5d 5b 70 2e 78 5d 29 0a 09 09 09 09 63 6f 6e y][p.x]).....con
3d20: 74 69 6e 75 65 3b 0a 09 09 09 56 5b 70 2e 79 5d tinue;....V[p.y]
3d30: 5b 70 2e 78 5d 20 3d 20 70 72 65 76 3b 0a 09 09 [p.x] = prev;...
3d40: 09 69 66 28 67 2e 6d 61 70 5b 70 5d 3d 3d 27 5c .if(g.map[p]=='\
3d50: 5c 27 20 7c 7c 20 67 2e 6d 61 70 5b 70 5d 3d 3d \' || g.map[p]==
3d60: 27 4f 27 29 0a 09 09 09 7b 0a 09 09 09 09 50 6f 'O')....{.....Po
3d70: 73 20 67 6f 62 61 63 6b 28 50 6f 73 20 70 29 20 s goback(Pos p)
3d80: 7b 0a 09 09 09 09 09 72 65 74 75 72 6e 20 56 5b {......return V[
3d90: 70 2e 79 5d 5b 70 2e 78 5d 3b 0a 09 09 09 09 7d p.y][p.x];.....}
3da0: 0a 09 09 09 09 66 6f 72 28 3b 3b 29 20 7b 0a 09 .....for(;;) {..
3db0: 09 09 09 09 50 6f 73 20 71 20 3d 20 67 6f 62 61 ....Pos q = goba
3dc0: 63 6b 28 70 29 3b 0a 09 09 09 09 09 69 66 28 71 ck(p);......if(q
3dd0: 20 3d 3d 20 67 2e 6d 61 70 2e 72 6f 62 6f 74 29 == g.map.robot)
3de0: 0a 09 09 09 09 09 09 69 66 28 71 2e 79 3d 3d 70 .......if(q.y==p
3df0: 2e 79 29 0a 09 09 09 09 09 09 09 72 65 74 75 72 .y)........retur
3e00: 6e 20 71 2e 78 3c 70 2e 78 20 3f 20 27 52 27 20 n q.x<p.x ? 'R'
3e10: 3a 20 27 4c 27 3b 0a 09 09 09 09 09 09 65 6c 73 : 'L';.......els
3e20: 65 0a 09 09 09 09 09 09 09 72 65 74 75 72 6e 20 e........return
3e30: 71 2e 79 3c 70 2e 79 20 3f 20 27 55 27 20 3a 20 q.y<p.y ? 'U' :
3e40: 27 44 27 3b 0a 09 09 09 09 09 70 3d 71 3b 0a 09 'D';......p=q;..
3e50: 09 09 09 7d 0a 09 09 09 7d 0a 0a 09 09 09 69 6e ...}....}.....in
3e60: 74 5b 34 5d 20 64 79 3d 5b 2d 31 2c 2b 31 2c 30 t[4] dy=[-1,+1,0
3e70: 2c 30 5d 3b 0a 09 09 09 69 6e 74 5b 34 5d 20 64 ,0];....int[4] d
3e80: 78 3d 5b 30 2c 30 2c 2d 31 2c 2b 31 5d 3b 0a 09 x=[0,0,-1,+1];..
3e90: 09 09 63 68 61 72 5b 5d 20 64 73 3d 5b 27 44 27 ..char[] ds=['D'
3ea0: 2c 27 55 27 2c 27 4c 27 2c 27 52 27 5d 3b 0a 09 ,'U','L','R'];..
3eb0: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
3ec0: 3c 34 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 69 <4; ++i) {.....i
3ed0: 66 28 67 2e 6d 61 70 2e 72 6f 62 6f 74 3d 3d 70 f(g.map.robot==p
3ee0: 20 26 26 20 64 65 61 74 68 2e 63 6f 75 6e 74 28 && death.count(
3ef0: 64 73 5b 69 5d 29 29 0a 09 09 09 09 09 63 6f 6e ds[i]))......con
3f00: 74 69 6e 75 65 3b 0a 09 09 09 09 69 6e 74 20 79 tinue;.....int y
3f10: 3d 70 2e 79 2b 64 79 5b 69 5d 2c 20 78 3d 70 2e =p.y+dy[i], x=p.
3f20: 78 2b 64 78 5b 69 5d 3b 0a 09 09 09 09 69 66 28 x+dx[i];.....if(
3f30: 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 (g.map[y,x]==' '
3f40: 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c ||g.map[y,x]=='\
3f50: 5c 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d \'||g.map[y,x]==
3f60: 27 2e 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d 3d '.'||g.map[y,x]=
3f70: 3d 27 4f 27 29 26 26 21 56 5b 79 5d 5b 78 5d 29 ='O')&&!V[y][x])
3f80: 20 7b 0a 09 09 09 09 09 51 2e 70 75 73 68 28 74 {......Q.push(t
3f90: 75 70 6c 65 28 6e 65 77 20 50 6f 73 28 79 2c 78 uple(new Pos(y,x
3fa0: 29 2c 70 29 2c 20 64 69 73 74 2b 31 29 3b 0a 09 ),p), dist+1);..
3fb0: 09 09 09 7d 0a 09 09 09 7d 0a 09 09 7d 0a 0a 09 ...}....}...}...
3fc0: 09 72 65 74 75 72 6e 20 27 57 27 3b 0a 09 7d 0a .return 'W';..}.
3fd0: 7d 0a 0a 2f 2f 61 6c 69 61 73 20 e4 be b5 e6 8e }..//alias .....
3fe0: a0 e5 a6 82 e7 81 ab 21 28 e7 96 be e5 a6 82 e9 .......!(.......
3ff0: a2 a8 29 20 4d 61 69 6e 53 6f 6c 76 65 72 3b 0a ..) MainSolver;.
4000: 2f 2f 61 6c 69 61 73 20 e4 be b5 e6 8e a0 e5 a6 //alias ........
4010: 82 e7 81 ab 21 28 e5 be 90 e5 a6 82 e6 9e 97 29 ....!(.........)
4020: 20 4d 61 69 6e 53 6f 6c 76 65 72 3b 0a 61 6c 69 MainSolver;.ali
4030: 61 73 20 e7 96 be e5 a6 82 e9 a2 a8 20 4d 61 69 as ......... Mai
4040: 6e 53 6f 6c 76 65 72 3b 0a 2f 2f 61 6c 69 61 73 nSolver;.//alias
4050: 20 e5 be 90 e5 a6 82 e6 9e 97 20 4d 61 69 6e 53 ......... MainS
4060: 6f 6c 76 65 72 3b 0a 2f 2f 61 6c 69 61 73 20 e4 olver;.//alias .
4070: b8 8d e5 8b 95 e5 a6 82 e5 b1 b1 20 4d 61 69 6e ........... Main
4080: 53 6f 6c 76 65 72 3b 0a Solver;.