Artifact 637ed2e24dcc1d56ef6afb96b9a6ad01448bc74f

• File SRM/425/1A.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#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;
	}
};