首页 > 试题广场 >

迷宫寻路

[编程题]迷宫寻路
  • 热度指数：16560 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。迷宫之中有的路上还有门，每扇门都在迷宫的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。请设计一个算法，帮助探险家找到脱困的最短路径。如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0-墙，1-路，2-探险家的起始位置，3-迷宫的出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙

输入描述:
迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N
后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。


输出描述:
路径的长度，是一个整数
示例1

输入

5 5
02111
01a0A
01003
01001
01111

输出

7
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-05 17:51:09
题解 难度：偏难 知识点：BFS 状态压缩 队列 思路： 如果不存在钥匙和锁的情况：（理解BFS过程） （将例子中的小写字母看为1，大写字母看为0）构成数组G[5][5] 起始位置G[0][1]，因此得到b[0][1]=0 【注】辅助数组b[i][j]用来记录从起始位置到坐标（i，j)一共的步数 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 模拟 运维工程师 前端工程师 算法工程师 测试工程师 2018 PHP工程师 拼多多 Java工程师
来自：拼多多2018校招内推...
上传者：小小
难度：
34条回答 22637浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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