首页 > 试题广场 >

迷宫问题

[编程题]迷宫问题
  • 热度指数：225838 时间限制：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)
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

迷宫问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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