Artifact 637ed2e24dcc1d56ef6afb96b9a6ad01448bc74f
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> point;
class CrazyBot
{
public:
double getProbability(int n, int east, int west, int south, int north)
{
set<point> vis;
vis.insert( point(0,0) );
vis.insert( point(0,1) );
return rec(vis, point(0,1), n-1, east, west, south, north);
}
double rec( set<point>& vis, point p, int N, int e, int w, int s, int n)
{
if( N == 0 )
return 1;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int pr[] = {e,w,s,n};
double ans = 0;
for(int i=0; i<4; ++i)
{
point q( p.first+dx[i], p.second+dy[i] );
if( !vis.count(q) )
{
vis.insert(q);
ans += double(pr[i])/100 * rec(vis, q, N-1, e, w, s, n);
vis.erase(q);
}
}
return ans;
}
};