首页 > 试题广场 >

走迷宫

[编程题]走迷宫
  • 热度指数：16093 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个 n \times m 的网格。你从起点 (x_s, y_s) 出发，每一次可以向上、下、左、右移动一步（若不超出边界）。某些格子上存在障碍物，无法经过。求从 (x_s, y_s) 移动到终点 (x_t, y_t) 的最少步数；若无法到达，输出 -1。

输入描述:
\hspace{15pt}在一行上输入两个整数 n, m \left(1 \leqq n, m \leqq 1000\right)，代表网格的行数与列数。
\hspace{15pt}在一行上输入四个整数 x_s, y_s, x_t, y_t \left(1 \leqq x_s, x_t \leqq n;\ 1 \leqq y_s, y_t \leqq m\right)，代表起点与终点的坐标。
\hspace{15pt}此后 n 行，第 i 行输入一个长度为 m 的字符串 g_i，其中
\hspace{23pt}\bullet\,若 g_{i, j}=\texttt{，表示第 i 行第 j 列为障碍物；
\hspace{23pt}\bullet\,若 g_{i, j}=\texttt{，表示该格子可通行。
\hspace{15pt}保证起点所在格子可通行。


输出描述:
\hspace{15pt}输出一个整数，表示最少移动次数；若无法到达，输出 -1。
示例1

输入

5 5
1 1 5 5
.....
****.
.....
**.**
.....

输出

12
示例2

输入

5 5
1 1 4 5
.....
****.
.....
**.**
.....

输出

-1
示例3

输入

5 5
1 1 5 5
.....
****.
.....
*****
.....

输出

-1
算法知识视频讲解
添加回答
JavaScript Node
好奇的六边形战士面向对象头像 好奇的六边形战士面向对象
const rl = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

// 构建异步迭代器，方便逐行读取输入
const iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 主逻辑函数
void async function main() {
    try {
        // 1. 读取网格尺寸 n 和 m
        const line1 = await readline();
        const [n, m] = line1.trim().split(' ').map(Number);
       
        // 2. 读取起点和终点坐标 (xs, ys) (xt, yt)
        const line2 = await readline();
        const [xs, ys, xt, yt] = line2.trim().split(' ').map(Number);
       
        // 转换为数组下标（输入是1开始，数组是0开始）
        const startX = xs - 1;
        const startY = ys - 1;
        const targetX = xt - 1;
        const targetY = yt - 1;
       
        // 3. 读取n行网格数据
        const grid = [];
        for (let i = 0; i < n; i++) {
            const row = await readline();
            grid.push(row.trim()); // 确保去除换行符等多余字符
        }
       
        // 4. 初始化BFS相关变量
        // 方向数组：上、下、左、右
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        // 访问标记数组：避免重复访问，同时记录步数
        const visited = new Array(n).fill(-1).map(() => new Array(m).fill(-1));
        // 队列：存储待访问的坐标 [x, y]
        const queue = [];
       
        // 起点入队，标记步数为0
        queue.push([startX, startY]);
        visited[startX][startY] = 0;
       
        // 5. 执行BFS
        let found = false;
        while (queue.length > 0 && !found) {
            const [x, y] = queue.shift(); // 取出队首元素（FIFO）
           
            // 到达终点，终止循环
            if (x === targetX && y === targetY) {
                found = true;
                break;
            }
           
            // 遍历四个方向
            for (const [dx, dy] of directions) {
                const newX = x + dx;
                const newY = y + dy;
               
                // 检查边界：newX和newY在合法范围内
                // 检查是否可通行：不是障碍物
                // 检查是否未被访问过：visited[newX][newY] === -1
                if (newX >= 0 && newX < n && newY >= 0 && newY < m
                    && grid[newX][newY] !== '*'
                    && visited[newX][newY] === -1) {
                   
                    // 标记步数（当前步数+1）
                    visited[newX][newY] = visited[x][y] + 1;
                    // 新坐标入队
                    queue.push([newX, newY]);
                }
            }
        }
       
        // 6. 输出结果：终点的步数（-1表示无法到达）
        console.log(visited[targetX][targetY]);
       
    } catch (error) {
        // 异常处理：防止输入格式错误导致程序崩溃
        console.log(-1);
    } finally {
        rl.close(); // 关闭输入流
    }
}();
发表于 2026-01-21 22:34:32 回复(0)
提交观点

问题信息

广度优先搜索(BFS)
难度：
1条回答 2071浏览

热门推荐

通过挑战的用户

查看代码

相关试题

走迷宫

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号