DFS深度优先搜索--JavaScript解法

迷宫问题

https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc

探寻路径问题:深度优先搜索+回溯

解题思路如下

  1. 首先构建原数组arr
  2. 定义存储路径的数组res,需要自己定义搜索顺序,本题搜索顺序为→ ↓ ← ↑
  3. 在搜索的过程中,需要知道该路径是否已经被搜索过,于是需要定义数组tftf[i][j]值为0为暂未搜索,tf[i][j]值为1为已搜索
  4. 定义深度优先搜索函数,若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,每次将满足条件的下标值pushres中,最终即可得到结果。
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]})`)
    }
}()
#算法#
全部评论

相关推荐

10-11 17:45
门头沟学院 Java
走吗:别怕 我以前也是这么认为 虽然一面就挂 但是颇有收获!
点赞 评论 收藏
分享
shtdbb_:还不错,没有让你做了笔试再挂你
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务