题解 | #迷宫问题# DFS解题

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
let arr = [];
let N, M;
// 记录当前路线下访问过的点
let viewed = new Set();
let direction = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
];
let endIndexX, endIndexY;
// 当前最短路线
let minSteps = [];

void (async function () {
    // Write your code here
    while ((line = await readline())) {
        arr.push(line.split(" ").map((a) => parseInt(a)));
    }

    N = arr[0][0];
    M = arr[0][1];
    arr.shift();
    [endIndexX, endIndexY] = [N - 1, M - 1];
    let startP = new Point(0, 0, []);
    dfs(startP);
    minSteps.unshift([startP.x, startP.y]);
    for (let i = 0; i < minSteps.length; i++) {
        console.log(`(${minSteps[i].join(",")})`);
    }
})();

class Point {
    constructor(x, y, steps = []) {
        this.x = x;
        this.y = y;
        this.steps = [...steps];
    }
}

var dfs = function (p) {
    if (p.x == endIndexX && p.y == endIndexY) {
        // 到达终点，记录当前路径 steps，获取最小路径
        // return minSteps;
        if(minSteps.length == 0) {
        minSteps = p.steps;
        } else {
        minSteps = p.steps.length < minSteps.length ? p.steps : minSteps;
        }
        return;
    }
    for (let i = 0; i < direction.length; i++) {
        let [_x, _y] = [p.x + direction[i][0], p.y + direction[i][1]];
        if (_x > N - 1 || _y > M - 1 || _x < 0 || _y < 0) {
        // 超出边界了
        continue;
        }
        // 遍历方位寻找可行的方向，下一点位值为 0 且在当前路径未访问过，就可以用
        if (arr[_x][_y] == 0 && !viewed.has(`${_x},${_y}`)) {
            // 防止走重复
            viewed.add(`${_x},${_y}`);
            p.steps.push([_x, _y]);
            let nextp = new Point(_x, _y, p.steps);
            dfs(nextp);
            // 探索其他路径
            viewed.delete(`${_x},${_y}`);
            p.steps.pop();
        }
    }
    return;
};