题解 | #迷宫问题# JS 版解法 - DFS

华为机试 43 题， 迷宫问题 。思路：深度优先搜索

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
const ipt = [];
rl.on("line", function (line) {
    ipt.push(line.split(' ').map(e => Number(e)));
}).on('close', function () {
    fun43(ipt);
});
function fun43(ipt) {
    let first = ipt.shift(), m = first[0], n = first[1], res = [], minSteps = Number.MAX_VALUE; // 初始化一些变量，minSteps代表目前为止的最小步数
    let visited = new Array(m).fill().map(() => new Array(n).fill(false));
    const dfs = (i, j, curRes) => {
        if (i < 0 || i >= m || j < 0 || j >= n || ipt[i][j] === 1 || visited[i][j]) return; // 如果索引值超出数组范围或者遇到墙壁或者当前位置已被访问过，则返回
        if (i === m - 1 && j === n - 1) {  // 如果当前位置是终点
            curRes.push(`(${i},${j})`);  // 那么将终点坐标 push 进当前结果 
            if (curRes.length < minSteps) {  // 如果当前结果步数小于目前为止的最小步数 minSteps，那就更新最终答案和 minSteps
                minSteps = curRes.length;
                res = [...curRes];
            }
            return;   // 返回
        }
        // 如果当前位置不是终点，那就把当前坐标 push 进入 curRes，并把当前位置设置为“访问过”，而后向上下左右四个方向递归
        // 最后一定要记得递归结束后要 pop 出当前坐标，并把当前位置设置为“未访问过”
        curRes.push(`(${i},${j})`);
        visited[i][j] = true;
        dfs(i + 1, j, curRes);
        dfs(i - 1, j, curRes);
        dfs(i, j + 1, curRes);
        dfs(i, j - 1, curRes);
        curRes.pop();
        visited[i][j] = false;
    };
    dfs(0, 0, []);   // 开始递归
    for (const e of res) {   // 输出结果
        console.log(e);
    }
}