DFS深度优先搜索--JavaScript解法
迷宫问题
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
探寻路径问题:深度优先搜索+回溯
解题思路如下
- 首先构建原数组
arr
- 定义存储路径的数组
res
,需要自己定义搜索顺序,本题搜索顺序为→ ↓ ← ↑
- 在搜索的过程中,需要知道该路径是否已经被搜索过,于是需要定义数组
tf
,tf[i][j]
值为0
为暂未搜索,tf[i][j]
值为1
为已搜索 - 定义深度优先搜索函数,若
x == n - 1 && y == m - 1
,则证明找到了终点,return
即可;若x < 0 || x >= n || y < 0 || y >= m
,则证明达到了边界;arr[x][y] == 1
,代表遇到了墙;tf[x][y] == 1
,代表路径已经被搜索过,都需要返回false
,探索过的路径需要将tf[i][j]
置为1
,每次将满足条件的下标值push
到res
中,最终即可得到结果。
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function () {
// Write your code here
const [n, m] = (await readline()).split(' ').map(Number)
let arr = Array(n).fill(null).map(() => Array(m).fill(0))
let k = 0
// 构建原数组[arr]
while (k < n) {
let tmp = (await readline()).split(' ').map(Number)
for (let i = 0; i < m; i++) {
arr[k][i] = tmp[i]
}
k++
}
// 寻找路径dfs
let res = []
// tf矩阵:寻找过得路径记为1
let tf = Array(n).fill(null).map(() => Array(m).fill(0))
function dfs(x, y) {
if (x == n - 1 && y == m - 1) {
res.push([x, y])
return true
}
// 边界条件
if (x < 0 || x >= n || y < 0 || y >= m || arr[x][y] == 1 || tf[x][y] == 1) {
return false
}
// 标记被搜索过的路径
tf[x][y] = 1
res.push([x, y])
// 搜索方向:右下左上
if (dfs(x + 1, y) || dfs(x, y + 1) || dfs(x - 1, y) || dfs(x, y - 1)) {
return true
}
res.pop()
}
dfs(0, 0)
for (let val of res) {
console.log(`(${val[0]},${val[1]})`)
}
}()
#算法#