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