首页 > 试题广场 >

迷宫问题

[编程题]迷宫问题
  • 热度指数：196119 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

定义一个二维数组 N*M ，如 5 × 5 数组下所示：


int maze[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,
};


它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。


数据范围： ， 输入的内容只包含


输入描述:
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。


输出描述:
左上角到右下角的最短路径，格式如样例所示。
示例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的博客 赞 (82) 回复(17) 收起
头像 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的博客 赞 (71) 回复(18) 收起
头像 空中转体一周半
发表于 2021-10-09 11:08:53
思路：广度优先遍历矩阵。代价相同的图中，广度优先遍历可以保证遍历到的目标点就是经过最短路径到达的点。为此，我们可以创建一个Point类，属性为横纵坐标和父节点。从（0，0）出发，将经过的坐标点都设为1，避免重复经过而进入死循环。把当前点的上下左右值为0的点都加入队列中，直到遇见出口为止。遇到出口时， 展开全文
去ta的博客 赞 (64) 回复(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的博客 赞 (58) 回复(3) 收起
头像 日不落拓海海
发表于 2022-02-19 17:45:03
最近突击学习了一下dfs，代码按dfs模板写完，突然就跑出正确答案了。中间的递归思想感觉自己还是没学清楚。不过看了下其他题解，有很多写法没有运用到dfs的核心思想，好多还要判断上下左右有没有墙，然后再决定往哪个方向走（这一步应该交给代码自己遍历。本题可以参考leetcode 200 岛屿数量http 展开全文
去ta的博客 赞 (48) 回复(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的博客 赞 (28) 回复(0) 收起
头像 牛客8008419号
发表于 2021-12-06 01:02:26
本题的重点就是要记录走过的点的坐标，因此创建lst=[(0,0)]列表，储存经过的点的坐标值。 lst[-1]即为当前所在点的坐标，如果该坐标与终点坐标重合，则break，输出lst。 如果未走到终点，则对当前走过的迷宫的点进行特别标注，表示已经走过——“walked。” 然后对当前点做判读，i代表 展开全文
去ta的博客 赞 (27) 回复(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) 收起
头像 牛客374676145号
发表于 2022-03-07 00:05:42
膜拜一位大神：ID叫“不太灵光的程序员”，思路是他的，我就是自己又写了一遍，缩小了一下行数。 def findway(x,y,path): if x == m-1 and y == n-1: [print(f'({l[0]},{l[1]})') for l in path] 展开全文
去ta的博客 赞 (17) 回复(1) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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