首页 > 试题广场 >

走迷宫

[编程题]走迷宫

热度指数：15289 时间限制：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$ 。

输入描述:

在一行上输入两个整数 ，代表网格的行数与列数。
在一行上输入四个整数 ，代表起点与终点的坐标。
此后  行，第  行输入一个长度为  的字符串 ，其中
若 ，表示第  行第  列为障碍物；
若 ，表示该格子可通行。
保证起点所在格子可通行。

输出描述:

输出一个整数，表示最少移动次数；若无法到达，输出 。

示例1

输入

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

输出

示例2

输入

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

输出

-1

示例3

输入

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

输出

-1

算法知识视频讲解

KEY.L

发表于 2022-07-09 21:47:25

题目描述给定一个n*m的二维整数数组，用来表示一个迷宫最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路展开全文

姐姐的遮阳伞

发表于 2022-04-16 15:23:50

深度优先遍历用例通过率: 30% 思路: 通过回溯法，找到起点到终点的所有路径。然后，在所有路径中取最小的那一个。这种方法仅适用于迷宫比较小的时候。如果迷宫很大，大概率超时了! 事实上，深度优先遍历(DFS)就不太适用于求最短路径，它一般适用于找路径的条数。 pub 展开全文

lxh666

发表于 2022-04-15 10:30:03

广度优先走过标记/不再走 //最短路径 import java.util.*; //最短路径 public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.i 展开全文

Linn在摸鱼

发表于 2022-09-20 12:59:29

r, c = map(int, input().split()) gs = [[1] * c for i in range(r)] k = input().sp 展开全文

哒不溜杰

发表于 2022-03-24 21:05:00

#include <queue> using namespace std; queue<pair<int, int> > q; const int N = 1001; char a[N][N]; int w[N][N]; bool b[N][N]; int x00 展开全文

Coming680

发表于 2022-03-19 14:30:09

首先，若使用回溯的方法会超时，代码如下所示： #include<iostream> #include<vector> #include<queue> #define INF 1e+7 using namespace std; typedef struct node 展开全文

什么又被限制

发表于 2022-10-19 15:24:01

#include <iostream> #include <algorithm> #include <queue> using namespace std; int n, m;//n行m列展开全文

JensYu

发表于 2023-09-30 17:19:03

n, m = map(int, input().split()) s_x, s_y, e_x, e_y = map(int, input().split()) mtr = [[1]* m for _ in range(n)] for i in range(n): row = input() 展开全文

_Bingbong

发表于 2024-12-12 17:10:32

解题思路 BFS求最短路径解题思路 1. 问题分析二维网格中找最短路径可以上下左右四个方向移动有障碍物不能通过需要判断是否能到达目标点 2. 解题步骤数据结构 - 使用二维数组存储网格 - 使用队列进行BFS - 使用二维数组记录距离 - 定义四个方向的移动：dx[] = {-1, 展开全文

饥饿的中国人offer多多

发表于 2025-08-09 22:49:25

import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 import java.util.*; public class Main { static int n, m; static int xs, ys, xe, ye 展开全文

问题信息

广度优先搜索(BFS)

难度：

31条回答 167收藏 1942浏览

通过挑战的用户

查看代码

牛客72914...

2022-10-08 08:08:51
duerduer冲啊

2022-10-04 21:25:59
这比赛怎么这么难打

2022-09-25 22:15:42
牛客20220...

2022-09-15 21:39:36
牛客74694...

2022-09-15 19:03:12

走迷宫

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题