Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-03-17SRM464(DIV2)

SRM464 div2 第三問(1000点)

| SRM464 div2 第三問(1000点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM464 div2 第三問(1000点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10742

得意の迷路問題。のはずだが一部のテストケースで落ちた。


import java.util.ArrayList;

public class ColorfulMazeTwo {

	public static int start_x;
	public static int start_y;
	public static int goal_x;
	public static int goal_y;
	public static int h;
	public static int w;
	public static double[][] max;
	public static double max_to_goal;

	public void getMax(String[] maze, int x, int y, double prob, ArrayList through, int[] trap) {
		if (x < 0 || x >= w || y < 0 || y >= h) return;
		char pt = maze[y].charAt(x);
		if (pt == '#') return;
		ArrayList through_b = new ArrayList(through);
		if (pt >= 'A' && pt <= 'G') {
			if (!through_b.contains(pt)) {
				through_b.add(pt);
				prob *= (double)(100 - trap[pt - 'A']) / 100f;
			}
		}
		if (max[y][x] < prob) {
			max[y][x] = prob;
		} else {
			return;
		}

		if (pt == '!') {
			if (max_to_goal < prob) {
				max_to_goal = prob;
				return;
			}
		}

		getMax(maze, x - 1, y, prob, through_b, trap);
		getMax(maze, x + 1, y, prob, through_b, trap);
		getMax(maze, x, y + 1, prob, through_b, trap);
		getMax(maze, x, y - 1, prob, through_b, trap);
		return;
	}


	public double getProbability(String[] maze, int[] trap) {
		h = maze.length;
		w = maze[0].length();
		max = new double[h][w];
		max_to_goal = 0;
		for (int y = 0 ; y < h ; y++) {
			for (int x = 0 ; x < w ; x++) {
				if (maze[y].charAt(x) == '$') {
					start_x = x;
					start_y = y;
				} else if (maze[y].charAt(x) == '!') {
					goal_x = x;
					goal_y = y;
				}
				max[y][x] = -1;
			}
		}
		getMax(maze, start_x, start_y, 1, new ArrayList(), trap);
		return max_to_goal;
	}

}

いろいろ使ってない変数があるのは見逃してください。