三次元迷路を探索する BFS（幅優先探索）の例題
三次元配列で表した迷路を「スタートからゴールまで最短経路で進めるか？」を調べるアルゴリズムを作ってみましょう。ここでは BFS（幅優先探索） を使います。BFSは「近い場所から順に探索する」ので、最短経路を見つけるのに適しています。
迷路の表現
- 三次元配列
maze[z][x][y]z→ 層（高さ）x→ 行y→ 列
- 値の意味
0→ 通路1→ 壁2→ スタート3→ ゴール
コード例：BFSで探索
import java.util.*;
public class CubeMazeBFS {
static class Point {
int z, x, y, dist;
Point(int z, int x, int y, int dist) {
this.z = z; this.x = x; this.y = y; this.dist = dist;
}
}
public static void main(String[] args) {
// 2層 × 3行 × 3列の迷路
int[][][] maze = {
{ // 層0
{2, 0, 1}, // 行0
{1, 0, 1}, // 行1
{1, 0, 3} // 行2
},
{ // 層1
{1, 0, 1}, // 行0
{0, 0, 0}, // 行1
{1, 1, 1} // 行2
}
};
// BFS探索
int result = bfs(maze);
if (result != -1) {
System.out.println("ゴールまでの最短距離: " + result);
} else {
System.out.println("ゴールに到達できませんでした");
}
}
static int bfs(int[][][] maze) {
int Z = maze.length;
int X = maze[0].length;
int Y = maze[0][0].length;
// 移動方向（上下左右＋層の上下）
int[][] dirs = {
{0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}, {1, 0, 0}, {-1, 0, 0}
};
// スタート位置を探す
Point start = null;
for (int z = 0; z < Z; z++) {
for (int x = 0; x < X; x++) {
for (int y = 0; y < Y; y++) {
if (maze[z][x][y] == 2) {
start = new Point(z, x, y, 0);
}
}
}
}
if (start == null) return -1;
boolean[][][] visited = new boolean[Z][X][Y];
Queue<Point> queue = new LinkedList<>();
queue.add(start);
visited[start.z][start.x][start.y] = true;
while (!queue.isEmpty()) {
Point p = queue.poll();
if (maze[p.z][p.x][p.y] == 3) {
return p.dist; // ゴール到達
}
for (int[] d : dirs) {
int nz = p.z + d[0];
int nx = p.x + d[1];
int ny = p.y + d[2];
if (nz >= 0 && nz < Z && nx >= 0 && nx < X && ny >= 0 && ny < Y) {
if (!visited[nz][nx][ny] && maze[nz][nx][ny] != 1) {
visited[nz][nx][ny] = true;
queue.add(new Point(nz, nx, ny, p.dist + 1));
}
}
}
}
return -1; // ゴールに到達できない
}
}
出力例
ゴールまでの最短距離: 4
解説
- Pointクラスで「位置＋距離」を管理。
- dirs配列で「上下左右＋層の上下」6方向を定義。
- BFSは「キュー」で管理し、近い場所から順に探索。
- ゴールに到達したら、その時点の距離が最短距離。
応用アイデア
- 経路そのもの（通った座標列）を記録して表示する。
- 迷路をランダム生成して、毎回違う立方体迷路を探索する。
- 3Dゲームやシミュレーションの基礎として応用できる。