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

AOJ 1144: カーリング2.0

競技プログラミング AOJ

問題

Curling 2.0 | Aizu Online Judge

f:id:kenkoooo:20150206023543g:plain

スタートのマスとゴールのマスが決まっている平面上で、駒をゴールまで運ぶ。駒は滑って移動するしかなく、障害物にぶつかるまで止まれない。ぶつかられた障害物は消滅する。フィールド外に出た場合は失敗となる時、最小で何回滑ればゴールにたどり着けるか。

解法

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;

    }
}