【Java】SRM 425 DIV2 Medium(500) - CrazyBot(深さ優先探索)

Problem Statement

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).

Definition

  • Class: CrazyBot
  • Method: getProbability
  • Parameters: int, int, int, int, int
  • Returns: double
  • Method signature: double getProbability(int n, int east, int west, int south, int north) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 64

Notes

  • Your return must have relative or absolute error less than 1E-9.

Constraints

  • n will be between 1 and 14, inclusive.
  • east will be between 0 and 100, inclusive.
  • west will be between 0 and 100, inclusive.
  • south will be between 0 and 100, inclusive.
  • north will be between 0 and 100, inclusive.
  • The sum of east, west, south and north will be 100.

Solution Plan

全ルートを探索する必要があるので、深さ優先探索を利用する。

Implementation

public class CrazyBot {

    boolean[][] grid = new boolean[100][100];
    int[] vx = {1, -1, 0, 0};
    int[] vy = {0, 0, -1, 1};

    double[] probability = new double[4];

    public double getProbability(int n, int east, int west, int south, int north) {
        probability[0] = east / 100.0;
        probability[1] = west / 100.0;
        probability[2] = south / 100.0;
        probability[3] = north / 100.0;

        return dfs(n, 50, 50);
    }

    private double dfs(int n, int x, int y) {

        if (grid[x][y]) return 0;
        if (n == 0) return 1;

        grid[x][y] = true;

        double p = 0.0;
        for (int i = 0; i < probability.length; i++) {
            p += probability[i] * dfs(n - 1, x + vx[i], y + vy[i]);
        }
        grid[x][y] = false;

        return p;
    }

}