読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 530 Div1 Medium: GogoXMarisaKirisima

競技プログラミング SRM

解法

まずは深さ優先探索でゴールする.1回のプレイで1回新しい行動をとるようにすれば,最大回数違う経路でプレイできる.

コード

public class GogoXMarisaKirisima {
	int N;
	private boolean[][] map;
	boolean[][] accessible;
	boolean visited[];

	public int solve(String[] choices) {
		N = choices.length;
		map = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = choices[i].charAt(j) == 'Y';
			}
		}

		accessible = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				accessible[i][j] = map[i][j];
			}
		}

		// 到達可能かをワーシャルフロイトで調べる
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (accessible[i][k] && accessible[k][j]) {
						accessible[i][j] = true;
					}
				}
			}
		}

		if (!accessible[0][N - 1]) {
			return 0;
		}

		visited = new boolean[N];
		return dfs(0);
	}

	private int dfs(int from) {
		int answer = 0;
		visited[from] = true;
		for (int to = 0; to < N; to++) {
			if (!map[from][to]) {
				continue;
			}

			if (visited[to] || to == N - 1) {
				// 初めて来たfromから行ったことのあるtoへ行くということは,新しい経路を通っているということ
				answer++;
			} else if (!visited[to] && accessible[to][N - 1]) {
				answer += dfs(to);
			}
		}
		return answer;
	}
}