AOJ 1144: カーリング2.0
問題
Curling 2.0 | Aizu Online Judge
スタートのマスとゴールのマスが決まっている平面上で、駒をゴールまで運ぶ。駒は滑って移動するしかなく、障害物にぶつかるまで止まれない。ぶつかられた障害物は消滅する。フィールド外に出た場合は失敗となる時、最小で何回滑ればゴールにたどり着けるか。
解法
DFS実装するだけ。「止まっている石は, 滑らせることによって動き出す. その時の方向は, すぐ次のマスに障害物がない方向ならどちらでもよい」や「1 回のゲーム中の滑らせる回数の最大は 10 である. この回数でゴールに石を到達させることができない場合, 失敗でゲームは終わる」という条件を見落としてて死んだ。
コード
import java.util.Scanner; public class Main { private static int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; private static int ans; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (true) { ans = 11; int w = sc.nextInt(); if (w == 0) { sc.close(); break; } int h = sc.nextInt(); int[][] field = new int[h][w]; int[] start = new int[2]; for (int i = 0; i < field.length; i++) { for (int j = 0; j < field[i].length; j++) { field[i][j] = sc.nextInt(); if (field[i][j] == 2) { // スタート地点の座標を保存しとく start[0] = i; start[1] = j; field[i][j] = 0; } } } int dfs = dfs(0, start[0], start[1], field); if (dfs > 10) { System.out.println(-1); } else { System.out.println(dfs); } } } static int dfs(int hit, int x, int y, int[][] field) { for (int d = 0; d < dir.length; d++) { int i = x; int j = y; i += dir[d][0]; j += dir[d][1]; if (i < 0 || i >= field.length || j < 0 || j >= field[i].length) { // フィールド外に出てしまった場合 continue; } else if (field[i][j] == 1) { // すぐ隣が石の場合 continue; } i -= dir[d][0]; j -= dir[d][1]; boolean next = true; while (true) { i += dir[d][0]; j += dir[d][1]; if (i < 0 || i >= field.length || j < 0 || j >= field[i].length) { // フィールド外に出てしまった場合 next = false; break; } if (field[i][j] == 1) { // 障害物があった時 break; } else if (field[i][j] == 3) { // ゴールだった時 return hit + 1; } } if (next && ans > hit + 1) { field[i][j] = 0; int hitdfs = dfs(hit + 1, i - dir[d][0], j - dir[d][1], field); field[i][j] = 1; ans = Math.min(ans, hitdfs); } } return ans; } }