矩阵最短路径DFS实现异常排查：终点(2,3)返回undefined无正确结果

问题根因 #

• 递归返回值未向上传递：四个方向调用shortestPath后没有将结果返回给上层调用，只有终点分支有返回值，其余分支无返回语句，最终顶层调用返回undefined。
• 非法分支无明确返回值：越界、走到不可通行单元格、已访问单元格的分支仅写了return，没有返回false，无法正确标识路径不可行。
• 逻辑不匹配需求：当前用DFS实现仅能判断是否存在可达路径，无法计算最短路径，求最短路径需改用BFS（广度优先遍历），优先遍历步数最少的层级。
• 全局变量污染：visited定义为全局变量，多次调用函数时不会重置，会导致后续调用结果错误。

修复可达性判断逻辑（修复返回undefined问题） #

function shortestPath(arr, c, r, visited = null) {
    // 初始化visited，避免全局变量污染
    if (!visited) {
        visited = Array.from({length: arr.length}, () => Array(arr[0].length).fill(false))
    }
    // 到达终点判断
    if (arr.length === c + 1 && arr[0].length === r + 1) {
        return arr[c][r] === 1;
    }
    // 越界/不可通行/已访问，直接返回false
    if (c >= arr.length || r >= arr[0].length || c < 0 || r < 0 || arr[c][r] === 0 || visited[c][r]) {
        return false
    }
    visited[c][r] = true
    // 四个方向递归，只要有一个方向能走到终点就返回true
    return shortestPath(arr, c, r + 1, visited)
        || shortestPath(arr, c + 1, r, visited)
        || shortestPath(arr, c, r - 1, visited)
        || shortestPath(arr, c - 1, r, visited)
}
let a = [[1, 1, 1, 0],
[1, 1, 0, 1],
[1, 1, 1, 1]]
console.log(shortestPath(a, 0, 0)) // 输出true

最短路径计算版本（BFS实现，匹配需求） #

function shortestPath(arr) {
    const rows = arr.length
    const cols = arr[0].length
    // 方向数组：右、下、左、上
    const dirs = [[0,1], [1,0], [0,-1], [-1,0]]
    // BFS队列，存储[行索引, 列索引, 当前步数]
    const queue = [[0, 0, 1]]
    const visited = Array.from({length: rows}, () => Array(cols).fill(false))
    visited[0][0] = true

    while(queue.length) {
        const [c, r, step] = queue.shift()
        // 到达终点直接返回步数
        if (c === rows - 1 && r === cols - 1) {
            return step
        }
        for (let [dc, dr] of dirs) {
            const nc = c + dc
            const nr = r + dr
            if (nc >=0 && nc < rows && nr >=0 && nr < cols && arr[nc][nr] === 1 && !visited[nc][nr]) {
                visited[nc][nr] = true
                queue.push([nc, nr, step + 1])
            }
        }
    }
    // 无可达路径返回-1
    return -1
}
let a = [[1, 1, 1, 0],
[1, 1, 0, 1],
[1, 1, 1, 1]]
console.log(shortestPath(a)) // 输出6

内容的提问来源于stack exchange，提问作者Stringer