题解 | #迷宫问题#

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 = [],
        list = [],
        arr = [];
    let num = 0;
    let n, m;
    let conrdin = [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0],
    ];
    while ((line = await readline())) {
        if (num == 0) {
            [n, m] = line.split(" ").map(Number);
            arr = Array.from(Array(n).fill(0), () => new Array(m).fill(0));
            num++;
        } else {
            maze.push(line.split(" ").map(Number));
            num++;
        }
    }
    // if (num == n + 1) {
    //     dfs(0, 0);
    //     console.log(list.join("\n"));
    // }

    function isRoad(x, y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
    function dfs(x, y) {
        // console.log(list)
        list.push("(" + x + "," + y + ")");
        arr[x][y] = 1;
        if (x == n - 1 && y == m - 1) return true;
        for (let i = 0; i < conrdin.length; i++) {
            tx = x + conrdin[i][0];
            ty = y + conrdin[i][1];
            if (isRoad(tx, ty) && arr[tx][ty] == 0 && maze[tx][ty] == 0) {
                if (dfs(tx, ty)) return true;
            }
        }
        list.pop();
        return false;
    }

    function isRoad(x, y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }

    dfs(0, 0);
    console.log(list.join("\n"));
})();

dfs做的事情：将（x,y）坐标push进入arr数组中，设定已经走过，对这个坐标的4个方向做相同操作。如果不满足，将（x，y）pop出去。xy无法组成通路