メニュー
検索
言語
タグ
迷路の行列を深さ優先探索で解き経路配列を返す関数 (solveMazeDFS)
総合評価: - 作成日: 2025-10-07
コメント:
Braveブラウザで動作確認済み。
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>solveMazeDFS</title>
<script>
/**
* 迷路matrixを深さ優先探索で攻略し、ゴールまでの経路をdstに格納する。
* dstに格納される座標はゴール地点からスタート地点に向かって格納される。
*
* dst ... 経路の保存先配列
* matrix ... 迷路を表す数値行列（2次元配列）
* pos ... 次に進む座標
* goal ... ゴールとなる座標
* floor ... 床を表す値
* wall ... 壁を表す値
* inf ... 無限大を表す値
* dirs ... 方角を表す座標配列
*
* 返り値 ... ゴールにたどり着いたら1, たどり着かなかったら0
*/
function solveMazeDFS (dst, matrix, {
pos=[0, 0],
goal=[10, 10],
floor=0,
wall=1,
inf=2,
dirs=[[0, -1], [1, 0], [0, 1], [-1, 0]],
}={}) {
const h = matrix.length
const w = matrix[0].length
const x = pos[0]
const y = pos[1]
const gx = goal[0]
const gy = goal[1]
if (x < 0 || x >= w || y < 0 || y >= h) {
// posが行列の範囲外
return 0
}
if (x === gx && y === gy) {
// ゴールにたどり着いた
dst.push(pos)
return 1
}
let c = matrix[y][x]
if (c === wall || c === inf) {
// 壁か通過済みで通れない
return 0
}
matrix[y][x] = inf // 通過済みのセルをマーク
// dirsの方向に進むことを試みる
for (const dir of dirs) {
const next = [x+dir[0], y+dir[1]]
let result = solveMazeDFS(dst, matrix, {
pos: next,
goal, floor, wall, inf, dirs,
})
if (result === 1) {
dst.push(next)
return result
}
}
return 0
}
document.addEventListener('DOMContentLoaded', () => {
let matrix, dst, result
// たどり着く迷路
matrix = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
dst = []
result = solveMazeDFS(dst, matrix, {
pos: [1, 1],
goal: [5, 7],
})
for (const pos of dst) {
matrix[pos[1]][pos[0]] = 3
}
console.assert(result === 1)
console.log(matrix)
// たどり着けない迷路
matrix = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
result = solveMazeDFS(dst, matrix, {
pos: [1, 1],
goal: [5, 7],
})
console.assert(result === 0)
// 引数で色々変える
matrix = [
[9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
[9, 1, 1, 1, 9, 1, 1, 1, 1, 9],
[9, 9, 9, 1, 9, 1, 9, 9, 1, 9],
[9, 1, 1, 1, 9, 1, 9, 1, 1, 9],
[9, 1, 9, 1, 9, 1, 9, 9, 9, 9],
[9, 1, 9, 1, 1, 1, 1, 1, 1, 9],
[9, 9, 9, 1, 9, 9, 9, 1, 9, 9],
[9, 1, 9, 1, 9, 1, 9, 1, 1, 9],
[9, 1, 1, 1, 9, 1, 1, 1, 9, 9],
[9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
]
dst = []
result = solveMazeDFS(dst, matrix, {
pos: [1, 1],
goal: [5, 7],
floor: 1,
wall: 9,
inf: 7,
})
for (const pos of dst) {
matrix[pos[1]][pos[0]] = 3
}
console.assert(result === 1)
console.log(matrix)
})
</script>
</head>
<body>
</body>
</html>