TopCoder SRM 530 Div1 Medium: GogoXMarisaKirisima
解法
まずは深さ優先探索でゴールする.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; } }