HJ148 迷宫寻路

• 题目
• 题解(43)
• 讨论(10)
• 排行

简单 通过率：44.72% 时间限制：1秒 空间限制：256M

知识点dfs

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

旺仔哥哥被困在一个 n×mn×m 的矩形迷宫里。每个格子要么是空地 (用符号 `.` 表示)，要么是墙 (用符号 `#` 表示)。旺仔哥哥只能从一个空地移动到其上下左右相邻的空地。
已知旺仔哥哥的起点为左上角 (1,1)(1,1)，终点为右下角 (n,m)(n,m)。请判断他是否能够到达终点。

输入描述：

第一行输入两个正整数 n,m (1≦n,m≦100)n,m (1≦n,m≦100)。
接下来的 nn 行每行输入一个长为 mm 的仅包含字符 `.` 与 `#` 的字符串，描述整个迷宫。
保证起点 (1,1)(1,1) 和终点 (n,m)(n,m) 均为空地。

输出描述：

若旺仔哥哥可以走到终点，则输出单词 YesYes；否则输出 NoNo。

示例1

输入：

3 5 .##.# .#... ...#.

复制输出：

Yes

复制说明：

路线如下：(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)

#include<bits/stdc++.h> using namespace std; const int N = 110; int n,m; char mp[N][N]; int dx[4]={-1,1,0,0},//四个方向 dy[4]={0,0,-1,1}; bool visited[N][N];//每个可遍历点的状态 void dfs(int x,int y)//深搜算法 { visited[x][y] = true;//将每次遍历到的点标记为true for(int i=0;i<4;i++) { int nx = x + dx[i], ny = y + dy[i]; //循环中四个方向会逐一排查 if(nx>=0 && nx<n && ny>=0 && ny<m && !visited[nx][ny] && mp[nx][ny] == '.') //满足边界条件（不能超出图的范围）并且该点没被遍历过,并且为'.' { dfs(nx,ny); //递归继续往后遍历 } } } int main() { cin>>n>>m; for(int i=0;i<n;i++)//将题目所给图输入 { for(int j=0;j<m;j++) { cin>>mp[i][j]; } } dfs(0,0);//调用dfs开始遍历，旺仔哥哥出发点为（0，0） //遍历完成后得到结果 //判断右下点是否为true，代码是0-based 注意要-1 if(visited[n-1][m-1]) cout<<"Yes"; else cout<<"No"; }