题解 | #迷宫问题#

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
    const nums = (await readline()).split(" ");
    let row = parseInt(nums[0].trim());
    let col = parseInt(nums[1].trim());
    let mxira = [];
    for (let i = 0; i < row; i++) {
        const item = await readline();
        mxira[i] = item.split(" ").map((i) => parseInt(i.trim()));
    }

    let index = searchPath(mxira);
    let val = []
    while(typeof index === 'number' && index >= 0){
        val.push(seq[index])
        index = seq[index].root;
    }
    val = val.reverse();
    for(let i of val){
        console.log(`(${i.y},${i.x})`)
    }
})();
let seq = [];

function searchPath(marix) {
    seq.push({
        root: null,
        y: 0,
        x: 0,
    });
    let index = 0;
    while (index < seq.length) {
        if (
            seq[index].x === marix[0].length - 1 &&
            seq[index].y === marix.length - 1
        ) {
            return index;
        }
        let points = getAblePoints(seq[index], marix);
        let i = 0;
        while (i < points.length) {
            if (!isVisit(points[i])) {
                seq.push(
                    Object.assign(points[i], {
                        root: index
                    })
                );
            }
            i++;
        }
        index++;
    }
}

function isVisit(point) {
    let index = 0;
    while (index < seq.length) {
        if (seq[index].x === point.x && seq[index].y === point.y) {
            return true;
        }
        index++;
    }
    return false;
}

function getAblePoints(point, marix) {
    let points = [];
    if (
        point.x < 0 ||
        point.y < 0 ||
        point.x > marix[0].length - 1 ||
        point.y > marix.length - 1
    )
        return points;

    if (point.x > 0 && marix[point.y][point.x - 1] !== 1) {
        points.push({ x: point.x - 1, y: point.y });
    }
    if (point.y > 0 && marix[point.y - 1][point.x] !== 1) {
        points.push({ x: point.x, y: point.y - 1 });
    }
    if (point.x < marix[0].length - 1 && marix[point.y][point.x + 1] !== 1) {
        points.push({ x: point.x + 1, y: point.y });
    }
    if (point.y < marix.length - 1 && marix[point.y + 1][point.x] !== 1) {
        points.push({ x: point.x, y: point.y + 1 });
    }
    return points;
}