演習課題「順番迷路」
2 次元のマス目で表される迷路が与えられます。その後、スタート地点 (sy, sx) と ゴール地点 (gy, gx) が順番に与えられるので、スタートからゴールまでの最短距離を求めてください。
制約
・ 入力はすべて整数
・ 1 ≦ h, w ≦ 10
・ 迷路の各マスは '.' (床マス) または '#' (壁マス) である
・ 各地点は 1 以上 h, w 以下の座標で表される
・ 与えられる地点は床マスである
・ スタート地点からゴール地点に到達することができる
期待する出力値
マス (2, 2) からマス (4, 2) までの最短距離は 12 です
＃04:最短経路問題
このチャプターでは、幅優先探索を利用して最短経路問題を解きます。
準備：
・空のキューを用意して、最初の頂点をキューに追加
・最短距離を記録する配列を INF で初期化し、最初の頂点の距離を 0 に設定
探索：
・キューが空になるまで、以下のことを繰り返す
1. キューから頂点を取り出す
2. 隣接する頂点を順番に見て、もしその頂点の距離が INF であれば、その頂点の距離を「今見ている頂点の距離 + 1」に更新してキューに追加する
5 4 1
1 2
1 3
2 4
2 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 final int INF = -1;
static int[] shortestPath(int n, List<List<Integer>> g, int s) {
// 空のキュー q を用意
Queue<Integer> q = new ArrayDeque<>();
// 最初の頂点 s をキューに追加
q.add(s);
// 最初の頂点からの距離を記録する配列 distance を用意
int[] distance = new int[n];
// 配列を INF で初期化
for (int i = 0; i < n; i++) {
distance[i] = INF;
}
// 最初の頂点 s の距離を 0 にする
distance[s] = 0;
// キューが空になるまで
while (!q.isEmpty()) {
// キューから頂点 v を取り出す
int v = q.poll();
// 隣接する頂点 u を順に見る
for (int u : g.get(v)) {
// もし頂点 u の距離が INF であれば
if (distance[u] == INF) {
// 頂点 u の距離を「頂点 v の距離 + 1」にする
distance[u] = distance[v] + 1;
// 頂点 u をキューに追加
q.add(u);
}
}
}
// 距離の配列を返す
return distance;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), s = sc.nextInt() - 1;
List<List<Integer>> graph = new ArrayList<List<Integer>>(n);
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<Integer>());
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt() - 1, b = sc.nextInt() - 1;
graph.get(a).add(b);
graph.get(b).add(a);
}
int[] distance = shortestPath(n, graph, s);
for (int i = 0; i < n; i++) {
System.out.println("頂点 " + s + " から頂点 " + (i + 1) + " への最短距離は " + distance[i] + " です");
}
sc.close();
}
}