3984 - BSFらしい 2012/09/23

3984 -- 迷宫问题

ぜんぜんわかってないけどBSF(Breadth-First Search) 幅優先探索というものらしい。

• 幅優先探索 - Wikipedia

キューとして、LinkedListを使ってます。

この解法は、えーとプログラミングコンテストチャレンジブックを参考にしてます。
なんで解けるのかよくわかってないです（笑）

プログラミングコンテストチャレンジブック
秋葉 拓哉 岩田 陽一 北川 宜稔


プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
秋葉拓哉 岩田陽一 北川宜稔



以下コードです。

package p3984_bsf;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static class P {
        int x, y;

        P(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int SIZE = 5;
    // 移動方向
    static int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };
    static int gx = 4, gy = 4;

    public static void main(String[] args) {

        int[][] MAZE = new int[SIZE][SIZE];
        Scanner scanner = new Scanner(System.in);
        {// READ 迷宮
            for (int i = 0; i < SIZE; i++) {
                String line = scanner.nextLine();
                String[] ss = line.split(" ");
                for (int j = 0; j < SIZE; j++) {
                    MAZE[i][j] = Integer.parseInt(ss[j]);
                }
            }
        }
        int INF = 1000000;
        int d[][] = new int[SIZE][SIZE];
        {
            Queue q = new LinkedList();
            for (int i = 0; i < SIZE; i++)
                for (int j = 0; j < SIZE; j++)
                    d[i][j] = INF;
            q.add(new P(0, 0));
            d[0][0] = 0;
            while (q.size() != 0) {
                P p = q.poll();
                if (p.x == gx && p.y == gy)
                    break;
                for (int i = 0; i < 4; i++) {
                    int nx = p.x + dx[i];
                    int ny = p.y + dy[i];
                    if (!(0 <= nx && nx < SIZE && 0 <= ny && ny < SIZE))
                        continue;
                    if (MAZE[nx][ny] == 0 && d[nx][ny] == INF) {
                        q.offer(new P(nx, ny));
                        d[nx][ny] = d[p.x][p.y] + 1;
                    }
                }

            }
            int n = 0;
            for (int i = 0; i < SIZE; i++)
                for (int j = 0; j < SIZE; j++) {
                    // System.out.printf("(x:%d y:%d):%d %n", i, j, d[i][j]);
                    if (d[i][j] == n) {
                        System.out.printf("(%d, %d)%n", i, j);
                        n++;
                    }
                }
        }

    }

}