题解 | #迷宫问题#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let line = await readline();
    let [m, n] = line.split(' ').map(Number);
    const matrix = [];
    const dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]];


    for (let i = 0; i < m; i++) {
        line = await readline();
        matrix.push(line.split(' ').map(Number));
    }

    let res = []
    const dfs = (x, y) => {
        // 如果当前位置越界或者被标记为1 则返回false
        if (x < 0 || y < 0 || x >= m || y >= n || matrix[x][y] === 1) return false

        // 能够进行这一步就存入结果列表
        res.push([x, y])

        // 标记为1 避免重复访问
        matrix[x][y] = 1

        // 抵达终点 返回 true 
        if(x === m - 1 && y === n - 1) {    
            return true
        }
        // 遍历四个方向，进行判断 => 最终能够抵达终点会接收到回溯回来的true， 那么继续返回true
        for(let [dx, dy] of dirs) {
            if(dfs(x + dx, y + dy)) return true
        }
        // 如果四个方向都没能找到终点，说明当前坐标不在路径上，需要从结果列表中弹出，返回false
        res.pop()
        /**
         * 还原路径 注意本题说明了只有一条路径，所以对于每一个位置只有两种情况：在路径上，或者是死胡同。并没有该位置在两条都能够通往终点的路径上这种情况。所以没有必要还原。
         * 但是如果有题目表示存在多条路径的话 不要忘记还原 
         * 比如以下迷宫有两条路径可以抵达终点，
         * 在第一次经过(2,2)时将其标记为1向上继续dfs会得到一个较长的路径，而我们会将该路径全部标记为1。 回溯到(2,2)时由于向上dfs时的路径未还原，走过的路便不能再走了，显然是不对的。
         *  0 1 0 0 0
         *  0 1 0 1 0
         *  0 0 0 0 0
         *  0 1 1 1 0
         *  0 0 0 1 0
         */
        matrix[x][y] = 0
        return false
    }
    // 从原点开始深度优先搜索
    dfs(0, 0)
    res.forEach(n => {
        console.log(`(${n[0]},${n[1]})`)
    })
}()