迷宫寻路
题目描述
机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 n × m n\times m n×m 矩阵,每个位置要么是空地,要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 ( 1 , 1 ) (1, 1) (1,1) 的位置,问能否走到 ( n , m ) (n, m) (n,m) 位置。
输入格式
第一行,两个正整数 n , m n,m n,m。
接下来
n
n
n 行,输入这个迷宫。每行输入一个长为
m
m
m 的字符串,#
表示墙,.
表示空地。
输出格式
仅一行,一个字符串。如果机器猫能走到
(
n
,
m
)
(n, m)
(n,m),则输出 Yes
;否则输出 No
。
样例 #1
样例输入 #1
3 5
.##.#
.#...
...#.
样例输出 #1
Yes
提示
样例解释
路线如下: ( 1 , 1 ) → ( 2 , 1 ) → ( 3 , 1 ) → ( 3 , 2 ) → ( 3 , 3 ) → ( 2 , 3 ) → ( 2 , 4 ) → ( 2 , 5 ) → ( 3 , 5 ) (1,1)\to (2,1) \to (3,1) \to (3,2)\to (3,3) \to (2, 3) \to (2, 4) \to (2, 5) \to (3, 5) (1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)
数据规模与约定
对于 100 % 100\% 100% 的数据,保证 1 ≤ n , m ≤ 100 1 \leq n, m \leq 100 1≤n,m≤100,且 ( 1 , 1 ) (1,1) (1,1) 和 ( n , m ) (n, m) (n,m) 均为空地。
深度搜索:
- 从(0,0)开始搜索,每次向上下左右走一步(注意是上下左右,而不只是往右下角走)
- 在走到目的地时退出
- 注意不能走出边界或者是遇到障碍物
- 设计数组对走过的路径进行标记,不能重复走,(
容易陷入循环
) - 每次调用dfs都要标记是否走过
#include<iostream>
using namespace std;
int n, m;//全局变量,用于退出条件的判断
char map[101][101];//设计图形数组,
bool v[101][101];//设计路径数组,进行判重
bool ans;//设计结果变量
int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };//循环遍历四个方向
bool in(int x, int y)//判断是否在有效的位置
{
return (x >= 0 && x < n&& y >= 0 && y < m);
}
bool dfs(int x, int y)//进行深度搜索
{
if (x == n - 1 && y == m - 1)//如果达到,直接退出
{
return true;
}
v[x][y] = true;//标记此处为真
for (int i = 0; i < 4; i++)//向四个方向走
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty))
{
if (map[tx][ty] == '.' && !v[tx][ty])
{
v[tx][ty];//记录路径
if (dfs(tx, ty))
{
return true;
}
}
}
}
v[x][y] = false;//还原路径
return false;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> map[i][j];
}
}
if (dfs(0, 0))
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
return 0;
}
广度优先搜索
- 用队列来判断是否结束,起到
延时处理
的目的 - 每次弹出一个量并进行处理与push操作,类似于波纹的操作,逐渐向后推
- 如果到达目的地退出
- 处理的条件于dfs相似
#include<iostream>
#include<queue>
using namespace std;
int n, m;
char map[101][101];
bool v[101][101];
bool ans;
int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };
struct node {//结构体的创建用于记录每个节点的数据
int x;
int y;
node(int xx, int yy)
{
x = xx;
y = yy;
}
};
bool in(int x, int y)
{
return (x >= 0 && x < n&& y >= 0 && y < m);
}
queue<node> S;
bool bfs(int x,int y)
{
S.push(node(x, y));
v[x][y] = true;
while (!S.empty())
{
node temp = S.front();//获取头节点
S.pop();//弹出头节点
//处理头节点
if (temp.x == n - 1 && temp.y == m - 1)
{
return true;
}
for (int i = 0; i < 4; i++)
{
int tx = temp.x + dir[i][0];
int ty = temp.y + dir[i][1];
if (in(tx, ty) && map[tx][ty] != '#' && !v[tx][ty])
{//符合条件将节点push,并且记录相应的路径
v[tx][ty] = true;
S.push(node(tx, ty));
}
}
}
return false;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> map[i][j];
}
}
if (bfs(0, 0))
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
return 0;
}