新・アルゴリズムとデータ構造入門Java編14: 幅優先探索・深さ優先探索

準備：
・座標を要素にとるキューを用意して、スタートの座標をキューに追加
・訪問済みかどうかを記録する 2 次元配列を未訪問で初期化し、スタートのマスを訪問済みに設定

探索：
・キューが空になるまで、以下のことを繰り返す
1. キューから座標を取り出す
2. 隣接するマスを順番に見て、もしそのマスが床マスで、未訪問であれば、訪問済みに設定して座標をキューに追加する

出力：
ゴールのマスが訪問済みなら Yes と出力し、そうでなければ No と出力する

5 5
1 1
5 5
.....
.#.#.
#..##
..##.
#....

5 5
1 1
5 5
.....
.#.#.
#..##
.###.
#....

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.ArrayDeque;

public class Main {

    static class Vec2 {
        int y;
        int x;

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

    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static void solveMaze(int h, int w, int[][] maze, int sy, int sx, int gy, int gx) {
        // 座標を要素にとるキュー q を用意
        Queue<Vec2> q = new ArrayDeque<>();
        // キューにスタートの座標 (sy, sx) を追加
        q.add(new Vec2(sy, sx));
        // 訪問済みかどうかを表す 2 次元配列 visited を用意
        boolean[][] visited = new boolean[h][w];
        // スタートのマス目を訪問済みにする
        visited[sy][sx] = true;

        // キューが空になるまで
        while (!q.isEmpty()) {
            // キューから座標 cur を取り出す
            Vec2 cur = q.poll();

            // i を 0 から 3 まで繰り返す
            for (int i = 0; i < 4; i++) {
                // 隣接するマスの座標 (ny, nx) を dx[i] と dy[i] を使って計算
                int ny = cur.y + dy[i];
                int nx = cur.x + dx[i];
                // もし、座標 (ny, nx) が範囲内で
                if (0 <= ny && ny < h && 0 <= nx && nx < w) {
                    // そのマスが床マスで、未訪問であれば
                    if (maze[ny][nx] == 0 && !visited[ny][nx]) {
                        // マスを訪問済みに設定
                        visited[ny][nx] = true;
                        // 座標 (ny, nx) をキューに追加
                        q.add(new Vec2(ny, nx));
                    }
                }
            }
        }

        // もし、ゴールのマスが訪問済みなら
        if (visited[gy][gx]) {
            // Yes と出力
            System.out.println("Yes");
        } else { // そうでなければ
            // No と出力
            System.out.println("No");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int h = sc.nextInt(), w = sc.nextInt();
        int sy = sc.nextInt() - 1, sx = sc.nextInt() - 1;
        int gy = sc.nextInt() - 1, gx = sc.nextInt() - 1;
        int[][] maze = new int[h][w];
        for (int i = 0; i < h; i++) {
            String line = sc.next();
            for (int j = 0; j < w; j++) {
                maze[i][j] = line.charAt(j) == '#' ? 1 : 0;
            }
        }

        solveMaze(h, w, maze, sy, sx, gy, gx);

        sc.close();
    }
}