题解 | #迷宫问题#

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
const inputArr = [];//存放输入的数据
let len = 1;
let m, n;
rl.on('line', function(line){
    if (len === 1) {
        m = line.split(' ').map(Number)[0];
        n = line.split(' ').map(Number)[1];
        len++;
    }else {
        inputArr.push(line.split(' ').map(Number));
    }
    
}).on('close', function(){
    fun(m,n,inputArr)//调用函数并输出
})
function fun(row, col,inputArr) {
    let minLine = [];//最短路径
    let nowLine = [];//当前路径
    let dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];//标识机器人可以走的方向
    let book = new Array(row).fill(0).map(()=>new Array(col).fill(0));
    let dfs = (x, y) => {
        nowLine.push(`(${x},${y})`);
        book[x][y] = 1;
        //如果走到最后一个位置
        if (x == row - 1 && y == col - 1) {
            //如果当前路径长度更短，则赋值给minline
            if (minLine.length == 0 || nowLine.length < minLine.length) {
                minLine = [];
                for (let i = 0; i < nowLine.length; i++) {
                    minLine[i] = nowLine[i];
                }
            }
            book[x][y] = 0;
            nowLine.pop();
            return;
        }
        for (let i = 0; i < 4; i++) {
            let tox = x + dir[i][0];
            let toy = y + dir[i][1];
            //可以走的位置是没有越界，无障碍物，没有走过的
            if (tox >= 0 && tox < row && toy >= 0 && toy < col && inputArr[tox][toy] == 0 && book[tox][toy] == 0) {
                dfs(tox, toy);
            }
        }
        book[x][y] = 0;
        nowLine.pop();
        return;
    }
    dfs(0, 0);
    for (let i = 0; i < minLine.length; i++) {
        console.log(minLine[i]);
    }
}