洛谷B3625 迷宫寻路 BFS与DFS双解法及其对比

题目描述

机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 n*m矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 (1, 1)的位置，问能否走到 (n, m) 位置。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

Yes

1. DFS解法

DFS模板参见 DFS

#include <bits/stdc++.h>
using namespace std;
char Map[101][101]; 
int done[101][101]={0}; //在地图上走的问题，都必须加上done这类标记数组，避免重复走导致程序死循环
int dy[4]={0,1,0,-1}; //(dx,dy)对应了上下左右四个方向
int dx[4]={1,0,-1,0};
bool flag = false;  //标记是否到达终点，若到达变为true，方便后面剪枝优化
int n,m;
int check(int x, int y)
{
	if(done[x][y]==1)  //已经走过该格子，不能再走上去
		return 0;
	if(Map[x][y]=='#') //迷宫的墙，不能走
		return 0;
	return 1;
}
void dfs(int x, int y)
{
	if(x==n&&y==m)  //判断是否到达终点
	{
		flag = true;
	}
	if(flag) 
		return ;
	
	if(x<1 || x>n ||y<1 || y>m)  //判断边界
		return ;
	for(int i=0;i<4;i++)  //遍历上下左右四个方向
	{
		int nowx = dx[i] + x; //定义当前（接下来）要走的格子
		int nowy = dy[i] + y;
		if(check(nowx,nowy))
		{
			done[x][y]=1;  //把先前的格子设为"已走过"
			dfs(nowx,nowy); 
          //此处不用回溯done[x][y]=0，不然会超时。
          //但是，如果题目问"从某点出发到某点走过路径的最大值"，那就需要回溯了
		}
	} 
}
int main()
{
  // 输入部分
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cin>>Map[i][j];
	}
	//题目给出从(1,1)走
	dfs(1,1);
  //输出部分
	if(flag)
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

2. BFS解法

BFS模板参见BFS

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
queue<PII> q;
PII temppair;
char Map[101][101];
int done[101][101]={0};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,m;
bool flag=false;

int check(int x,int y)
{
	if(x<1||x>n||y<1||y>m)
		return 0;
	if(done[x][y]==1)
		return 0;
	if(Map[x][y]=='#')
		return 0;
	return 1;
}

void bfs()
{
	while(!q.empty())
	{
		if(q.front().first==n&&q.front().second==m) //判断当前点是否是终点(n,m)
			flag = true;
		if(flag)
			return ;
		temppair = q.front();  //从这往下是标准的BFS模板
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nowx=temppair.first+dx[i];
			int nowy=temppair.second+dy[i];
			if(check(nowx,nowy))
			{
				q.push({nowx,nowy});
				done[nowx][nowy]=1;
			}
		}
		
	}
	return ;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>Map[i][j];
	q.push({1,1}); //将起点(1,1)压入队列
	bfs();
	if(flag)
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

3.对比

由于这道题不需要回溯，用DFS时如果硬套模板，会导致部分评测TLE。
在代码书写复杂度上，DFS>BFS；
在程序运行时间、占用内存上未剪枝的DFS>剪枝的DFS≈BFS。