题解 | #迷宫问题# DFS + 回溯

JS Node ACM 模式

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
    let maze = [];
    while ((line = await readline())) {
        maze.push(line.split(" ").map(Number));
    }
    let coos = maze.shift();
    let row = coos[0],
        col = coos[1];
    let path = [];

    function dfs(r, c) {
        // 1. 判断当前位置是否在迷宫内
        if (r < 0 || r >= row || c < 0 || c >= col || maze[r][c] === 1)
            return false;
        // 2. 当前位置在迷宫内, 标记当前位置为已走过（1）、
        //    将当前位置记入path
        maze[r][c] = 1;
        path.push([r, c]);
        // 3. 判断路径是否结束（走到终点）
        if (r === row - 1 && c === col - 1) return true;
        // 4. 路径没有结束，向四个方向寻找下一位置
        if (dfs(r + 1, c) || dfs(r - 1, c) || dfs(r, c + 1) || dfs(r, c - 1))
            return true;
        // 5. 没找到合法位置，回溯、退出
        path.pop();
        return false;
    }

    dfs(0, 0);

    for (p of path) {
        console.log(`(${p[0]},${p[1]})`);
    }
})();