SRM425 CrazyBot

An out-of-control robot is placed on a plane, and it takes n random steps. At each step, the robot chooses one of four directions randomly and moves one unit in that direction. The probabilities of the robot choosing north, south, east or west are north, south, east and west percent, respectively.

The robot’s path is considered simple if it never visits the same point more than once. (The robot’s starting point is always the first visited point.) Return a double containing the probability that the robot’s path is simple. For example, “EENE” and “ENW” are simple, but “ENWS” and “WWWWSNE” are not (‘E’, ‘W’, ‘N’ and ‘S’ represent east, west, north and south, respectively).

using namespace std;

bool grid[100][100] = {false};
int vx[] = {1, -1, 0, 0};
int vy[] = {0, 0, -1, -1};
double prob[4];

class CrazyBot {
    public:
        double getProbability(int n, int east, int west, int south, int north)
    {
        prob[0] = east / 100.0;
        prob[0] = west / 100.0;
        prob[0] = south / 100.0;
        prob[0] = north / 100.0;

        return dfs(50, 50, n);
    }

    double dfs(int x, int y, int n){
        if(grid[x][y]) return 0;
        if (n == 0) return 1;

        grid[x][y] = true;
        double ret = 0;

        for(int i = 0; i < 4; i++){
            ret += dfs(x + vx[i], y + vy[i], n - 1) * prob[i];
        }
        grid[x][y] = false;

        return ret;
    }
}