DT走过的路

描述

$$有一个 $h$h 行 $w$w 列的网格，我们使用 $(i,j)$(i,j) 表示网格中从上往下数第 $i$i 行和从左往右数第 $j$j 列的单元格。每个方格要么是可以通过的空方格 $\mathtt{\text{‘0’}}$‘0’ ，要么是不可通过的墙方格 $\mathtt{\text{‘1’}}$‘1’ ，特别的，网格的四周都是墙方格，你可以沿着空方格上下左右随意移动：从 $(x,y)$(x,y) 向上移动一格即抵达 $(x-1,y)$(x−1,y) 、向下移动一格即抵达 $(x+1,y)$(x+1,y) 、向左移动一格即抵达 $(x,y-1)$(x,y−1) 、向右移动一格即抵达 $(x,y+1)$(x,y+1) 。

$$现在，你位于迷宫的入口 $(0,0)$(0,0) ，想要前往终点 $(h-1,w-1)$(h−1,w−1) 。请输出一条从起点到终点的可行路径。

$$保证起点和终点一定为空方格，你始终可以找到且能唯一找到一条从起点出发到达终点的可行路径。

输入描述：

$$第一行输入两个整数 $h,w(1\leqq h,w\leqq 100)$h,w(1≦h,w≦100) 代表迷宫的行数和列数。
$$此后 $h$h 行，第 $i$i 行输入 $w$w 个整数 $a_{i,1},a_{i,2},\dots ,a_{i,w}(0\leqq a_{i,j}\leqq 1)$ai,1​,ai,2​,…,ai,w​(0≦ai,j​≦1) 代表迷宫的布局。其中，$a_{i,j}=0$ai,j​=0 表示单元格 $(i,j)$(i,j) 是空方格，$a_{i,j}=1$ai,j​=1 表示单元格 $(i,j)$(i,j) 是墙方格。

输出描述：

$$输出若干行，第 $i$i 行输出两个整数 $x_i,y_i$xi​,yi​ ，表示路径的第 $i$i 步抵达的单元格坐标为 $(x_i,y_i)$(xi​,yi​) 。

$$你需要保证输出的路径是符合题目要求的，即从起点 $(0,0)$(0,0) 出发，到达终点 $(h-1,w-1)$(h−1,w−1) ，且路径上每个单元格都是空方格，行走的单元格都是彼此相邻的。

示例1

输入：

5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

复制

输出：

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

复制

示例2

输入：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0

复制

输出：

(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

思路：

1. 读入数组，二维
2. 采用BFS入队出队方式，通过判断是否走到底，是否有未出队
3. 四个方向处理
4. 需要记录上一步及当前坐标是否走过
5. 回溯方式

void (async function () {
    // Write your code here
    const [h, w] = (await readline()).split(" ").map(Number);
    const grid = [];
    for (let i = 0; i < h; i++) {
        grid[i] = (await readline()).split(" ");
    }

    //console.log(grid)
    const dirs = [
        [-1, 0],
        [1, 0],
        [0, 1],
        [0, -1],
    ];
    const queue = [];
    const res = [];
    const pre = Array.from({ length: h }, () => Array(w).fill(null));
    const visited = Array.from({ length: h }, () => Array(w).fill(false));
    let isEnd = false;
    visited[0][0] = true;
    queue.push([0, 0]);
    //console.log(grid);
    while (queue.length && !isEnd) {
        const [x, y] = queue.shift();
        if (x === h - 1 && y === w - 1) {
            isEnd = true;
            //console.log("结束", x, y);
            break;
        }
        for (const [dx, dy] of dirs) {
            const tempX = x + dx;
            const tempY = y + dy;
            if (
                tempX >= 0 &&
                tempX < h &&
                tempY >= 0 &&
                tempY < w &&
                grid[tempX][tempY] === "0" &&
                !visited[tempX][tempY]
            ) {
                //console.log([tempX, tempY]);
                queue.push([tempX, tempY]);
                visited[tempX][tempY] = true;
                pre[tempX][tempY] = [x, y];
            }
        }
    }
    console.log(pre, "pre");

    let path = [];
    let cur = [h - 1, w - 1];
    while (cur) {
        path.unshift(cur);
        cur = pre[cur[0]][cur[1]];
    }
    console.log(path);
    for (const [i, j] of path) {
        console.log(`(${i},${j})`);
    }
})();