迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 $n\times m$ 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 $(1,1)$ 的位置，问能否走到 $(n,m)$ 位置。

输入格式

第一行，两个正整数 $n,m$。

接下来 $n$ 行，输入这个迷宫。每行输入一个长为 $m$ 的字符串，# 表示墙，. 表示空地。

输出格式

仅一行，一个字符串。如果机器猫能走到 $(n,m)$，则输出 Yes；否则输出 No。

样例 #1

样例输入 #1

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

样例输出 #1

Yes

提示

样例解释

路线如下：$(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)$

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n,m\le 100$，且 $(1,1)$ 和 $(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;
}