首页 > 试题广场 >

迷宫问题

[编程题]迷宫问题
  • 热度指数：212961 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}有一个 h 行 w 列的网格，我们使用 (i,j) 表示网格中从上往下数第 i 行和从左往右数第 j 列的单元格。每个方格要么是可以通过的空方格 \texttt{`0'} ，要么是不可通过的墙方格 \texttt{`1'} ，特别的，网格的四周都是墙方格，你可以沿着空方格上下左右随意移动：从 (x,y) 向上移动一格即抵达 (x-1,y) 、向下移动一格即抵达 (x+1,y) 、向左移动一格即抵达 (x,y-1) 、向右移动一格即抵达 (x,y+1) 。
\hspace{15pt}现在，你位于迷宫的入口 (0,0) ，想要前往终点 (h-1,w-1) 。请输出一条从起点到终点的可行路径。

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

输入描述:
\hspace{15pt}第一行输入两个整数 h,w\left(1 \leqq h, w \leqq 100\right) 代表迷宫的行数和列数。
\hspace{15pt}此后 h 行，第 i 行输入 w 个整数 a_{i,1}, a_{i,2}, \dots, a_{i,w}\left(0 \leqq a_{i,j} \leqq 1\right) 代表迷宫的布局。其中，a_{i,j}=0 表示单元格 (i,j) 是空方格，a_{i,j}=1 表示单元格 (i,j) 是墙方格。


输出描述:
\hspace{15pt}输出若干行，第 i 行输出两个整数 x_i,y_i ，表示路径的第 i 步抵达的单元格坐标为 (x_i,y_i) 。

\hspace{15pt}你需要保证输出的路径是符合题目要求的，即从起点 (0,0) 出发，到达终点 (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)
算法知识视频讲解
开通博客
头像 旅丶途
发表于 2021-10-20 21:30:36
import java.util.*; // 题目已经提示了 【迷宫只有一条通道】，则直接使用 DFS 找路径就行了，如不有多条路径找最短考虑使用 BFS public class Main { public static void main(String[] args) { 展开全文
去ta的博客 赞 (90) 回复(19) 收起
头像 BSF
发表于 2021-10-21 21:13:11
while True: try: m, n = list(map(int, input().split())) maze = [] for _ in range(m): maze.append(list(map(int 展开全文
去ta的博客 赞 (78) 回复(19) 收起
头像 空中转体一周半
发表于 2021-10-09 11:08:53
思路：广度优先遍历矩阵。代价相同的图中，广度优先遍历可以保证遍历到的目标点就是经过最短路径到达的点。为此，我们可以创建一个Point类，属性为横纵坐标和父节点。从（0，0）出发，将经过的坐标点都设为1，避免重复经过而进入死循环。把当前点的上下左右值为0的点都加入队列中，直到遇见出口为止。遇到出口时， 展开全文
去ta的博客 赞 (68) 回复(14) 收起
头像 我是一颗大白菜__
发表于 2021-09-25 14:46:04
#include<iostream> #include<vector> using namespace std; int n,m; vector<vector<int>> maze; //当从（0，0）到（n-1，m-1）有多条通路时，best_pa 展开全文
去ta的博客 赞 (64) 回复(3) 收起
头像 日不落拓海海
发表于 2022-02-19 17:45:03
最近突击学习了一下dfs，代码按dfs模板写完，突然就跑出正确答案了。中间的递归思想感觉自己还是没学清楚。不过看了下其他题解，有很多写法没有运用到dfs的核心思想，好多还要判断上下左右有没有墙，然后再决定往哪个方向走（这一步应该交给代码自己遍历。本题可以参考leetcode 200 岛屿数量http 展开全文
去ta的博客 赞 (56) 回复(8) 收起
头像 陶陶2021
发表于 2021-10-08 20:47:35
import java.util.*; public class Main { public static ArrayList<int[]> path = new ArrayList<>();//搜索所有可能的路径 public static ArrayLi 展开全文
去ta的博客 赞 (31) 回复(0) 收起
头像 牛客8008419号
发表于 2021-12-06 01:02:26
本题的重点就是要记录走过的点的坐标，因此创建lst=[(0,0)]列表，储存经过的点的坐标值。 lst[-1]即为当前所在点的坐标，如果该坐标与终点坐标重合，则break，输出lst。 如果未走到终点，则对当前走过的迷宫的点进行特别标注，表示已经走过——“walked。” 然后对当前点做判读，i代表 展开全文
去ta的博客 赞 (31) 回复(6) 收起
头像 冲就完事
发表于 2020-04-16 07:07:03
为何是真正？因为看了下别人的python 解法，都有个弊端，就是只能做从起点0到终点的唯一路径的题，如果出现分支，或者多路径求最短那么那些方法就不适用了。相对而言，以下做法不仅可以实现多路径下的最短到终点探索，还能实现任意两点之间的最短路径返回，而且代码还不长，符合python人生苦短特点，所以成为 展开全文
去ta的博客 赞 (24) 回复(3) 收起
头像 他乡客和异乡人
发表于 2020-08-07 12:23:40
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.Stack; public cl 展开全文
去ta的博客 赞 (19) 回复(3) 收起
头像 VenshaoJoe
发表于 2022-07-16 18:06:13
采用DFS找到通路即可。 假设有一个函数F，给定坐标 (i, j) 即可判断经过此坐标能否达目的地。 考虑一下几种情况： 最简单的情况：(i, j) 已经是目的地，我们返回 true 表示经过此坐标能到达目的地 基于坐标 (i, j) 可以 展开全文
去ta的博客 赞 (18) 回复(1) 收起

问题信息

dfs 查找 广度优先搜索(BFS)
难度：
601条回答 104737浏览

热门推荐

通过挑战的用户

查看代码

相关试题

迷宫问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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