Artifact 637ed2e24dcc1d56ef6afb96b9a6ad01448bc74f:
0000: 23 69 6e 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 #include <vector
0010: 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 >.#include <stri
0020: 6e 67 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c ng>.#include <al
0030: 67 6f 72 69 74 68 6d 3e 0a 23 69 6e 63 6c 75 64 gorithm>.#includ
0040: 65 20 3c 6d 61 70 3e 0a 23 69 6e 63 6c 75 64 65 e <map>.#include
0050: 20 3c 73 65 74 3e 0a 75 73 69 6e 67 20 6e 61 6d <set>.using nam
0060: 65 73 70 61 63 65 20 73 74 64 3b 0a 0a 74 79 70 espace std;..typ
0070: 65 64 65 66 20 70 61 69 72 3c 69 6e 74 2c 69 6e edef pair<int,in
0080: 74 3e 20 70 6f 69 6e 74 3b 0a 0a 63 6c 61 73 73 t> point;..class
0090: 20 43 72 61 7a 79 42 6f 74 0a 7b 0a 70 75 62 6c CrazyBot.{.publ
00a0: 69 63 3a 0a 09 64 6f 75 62 6c 65 20 67 65 74 50 ic:..double getP
00b0: 72 6f 62 61 62 69 6c 69 74 79 28 69 6e 74 20 6e robability(int n
00c0: 2c 20 69 6e 74 20 65 61 73 74 2c 20 69 6e 74 20 , int east, int
00d0: 77 65 73 74 2c 20 69 6e 74 20 73 6f 75 74 68 2c west, int south,
00e0: 20 69 6e 74 20 6e 6f 72 74 68 29 0a 09 7b 0a 09 int north)..{..
00f0: 09 73 65 74 3c 70 6f 69 6e 74 3e 20 76 69 73 3b .set<point> vis;
0100: 0a 09 09 76 69 73 2e 69 6e 73 65 72 74 28 20 70 ...vis.insert( p
0110: 6f 69 6e 74 28 30 2c 30 29 20 29 3b 0a 09 09 76 oint(0,0) );...v
0120: 69 73 2e 69 6e 73 65 72 74 28 20 70 6f 69 6e 74 is.insert( point
0130: 28 30 2c 31 29 20 29 3b 0a 09 09 72 65 74 75 72 (0,1) );...retur
0140: 6e 20 72 65 63 28 76 69 73 2c 20 70 6f 69 6e 74 n rec(vis, point
0150: 28 30 2c 31 29 2c 20 6e 2d 31 2c 20 65 61 73 74 (0,1), n-1, east
0160: 2c 20 77 65 73 74 2c 20 73 6f 75 74 68 2c 20 6e , west, south, n
0170: 6f 72 74 68 29 3b 0a 09 7d 0a 0a 09 64 6f 75 62 orth);..}...doub
0180: 6c 65 20 72 65 63 28 20 73 65 74 3c 70 6f 69 6e le rec( set<poin
0190: 74 3e 26 20 76 69 73 2c 20 70 6f 69 6e 74 20 70 t>& vis, point p
01a0: 2c 20 69 6e 74 20 4e 2c 20 69 6e 74 20 65 2c 20 , int N, int e,
01b0: 69 6e 74 20 77 2c 20 69 6e 74 20 73 2c 20 69 6e int w, int s, in
01c0: 74 20 6e 29 0a 09 7b 0a 09 09 69 66 28 20 4e 20 t n)..{...if( N
01d0: 3d 3d 20 30 20 29 0a 09 09 09 72 65 74 75 72 6e == 0 )....return
01e0: 20 31 3b 0a 09 09 69 6e 74 20 64 78 5b 5d 20 3d 1;...int dx[] =
01f0: 20 7b 30 2c 30 2c 31 2c 2d 31 7d 3b 0a 09 09 69 {0,0,1,-1};...i
0200: 6e 74 20 64 79 5b 5d 20 3d 20 7b 31 2c 2d 31 2c nt dy[] = {1,-1,
0210: 30 2c 30 7d 3b 0a 09 09 69 6e 74 20 70 72 5b 5d 0,0};...int pr[]
0220: 20 3d 20 7b 65 2c 77 2c 73 2c 6e 7d 3b 0a 09 09 = {e,w,s,n};...
0230: 64 6f 75 62 6c 65 20 61 6e 73 20 3d 20 30 3b 0a double ans = 0;.
0240: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0250: 3c 34 3b 20 2b 2b 69 29 0a 09 09 7b 0a 09 09 09 <4; ++i)...{....
0260: 70 6f 69 6e 74 20 71 28 20 70 2e 66 69 72 73 74 point q( p.first
0270: 2b 64 78 5b 69 5d 2c 20 70 2e 73 65 63 6f 6e 64 +dx[i], p.second
0280: 2b 64 79 5b 69 5d 20 29 3b 0a 09 09 09 69 66 28 +dy[i] );....if(
0290: 20 21 76 69 73 2e 63 6f 75 6e 74 28 71 29 20 29 !vis.count(q) )
02a0: 0a 09 09 09 7b 0a 09 09 09 09 76 69 73 2e 69 6e ....{.....vis.in
02b0: 73 65 72 74 28 71 29 3b 0a 09 09 09 09 61 6e 73 sert(q);.....ans
02c0: 20 2b 3d 20 64 6f 75 62 6c 65 28 70 72 5b 69 5d += double(pr[i]
02d0: 29 2f 31 30 30 20 2a 20 72 65 63 28 76 69 73 2c )/100 * rec(vis,
02e0: 20 71 2c 20 4e 2d 31 2c 20 65 2c 20 77 2c 20 73 q, N-1, e, w, s
02f0: 2c 20 6e 29 3b 0a 09 09 09 09 76 69 73 2e 65 72 , n);.....vis.er
0300: 61 73 65 28 71 29 3b 0a 09 09 09 7d 0a 09 09 7d ase(q);....}...}
0310: 0a 09 09 72 65 74 75 72 6e 20 61 6e 73 3b 0a 09 ...return ans;..
0320: 7d 0a 7d 3b 0a }.};.