DFS求解迷宫问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了DFS求解迷宫问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

dfs迷宫问题,深度优先,算法,图论

下面来具体分析一下算法的具体实现

首先要进行搜索，对搜索方向的顺序规定为：右-->下-->左-->上

dfs迷宫问题,深度优先,算法,图论

按照搜索顺序从起点开始搜索，在搜索的过程中将已经搜索过的位置设为已访问，这样我们就可以得到如下图所示的一条路线。

dfs迷宫问题,深度优先,算法,图论

在到达终点后要进行回溯，利用回溯找到其他路径，最终得出一个最短路径。下图蓝色箭头代表回溯路径，黄色箭头为回溯得出的新路径（其他路径就不在图中画出）。通过多次回溯发现最短路径step=7

dfs迷宫问题,深度优先,算法,图论

DFS求解迷宫问题的关键是利用回溯来找到最短路径，在代码实现上即是递归。通过二维数组

a[N][N]来表示地图上的空地和障碍物，二维数组v[N][N]数组来表示空地是否访问。

#include<cstdio>
using namespace std;
int m,n,p,q,min=99999999;//p,q是终点坐标 
int a[100][100];//地图 ,其中1表示空地，2表示障碍物 
int v[100][100]; //0表示未访问，1表示已访问 
void dfs(int x,int y,int step)
{
	if(x==p && y==q)
	{
		if(step<min)	
		min=step;
		return;//回溯 
	}
	//顺时针试探
	//右
	if(a[x][y+1]==1 && v[x][y+1]==0)
	{
		v[x][y+1]=1;
		dfs(x,y+1,step+1);
		v[x][y+1]=0;
	} 
	//下 
	if(a[x+1][y]==1 && v[x+1][y]==0)
	{
		v[x+1][y]=1;
		dfs(x+1,y,step+1);
		v[x+1][y]=0;
	} 
	//左
	if(a[x][y-1]==1 && v[x][y-1]==0)
	{
		v[x][y-1]=1;
		dfs(x,y-1-1,step+1);
		v[x][y-1]=0;
	} 
	//上 
	if(a[x-1][y]==1 && v[x-1][y]==0)
	{
		v[x-1][y]=1;
		dfs(x-1,y,step+1);
		v[x-1][y]=0;
	} 
	return;
}

上述代码我们可以进行优化，将四个方向通过一个循环来实现就可以大大缩减代码量。

向右移动x不变，y+1；向下移动x+1，y不变；向左移动x不变，y-1;向上移动x-1,y不变。

dfs迷宫问题,深度优先,算法,图论

通过x,y值的变化我们可以通过两个方向数组dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}来表示不同的方向，

再通过tx=x+dx,ty=y+dy就可以实现方向的变化

#include<cstdio>
using namespace std;
int m,n,p,q,min=99999999;//p,q是终点坐标 
int a[100][100];//地图 ,其中1表示空地，2表示障碍物 
int v[100][100]; //0表示未访问，1表示已访问 
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0}; 
void dfs(int x,int y,int step){
	if(x==p && y==q)
	{
		if(step<min)	
		min=step;
		return;//回溯 
	}
	for(int k=0;k<=3;k++)
	{
		int tx,ty;
		tx=x+dx[k];
		ty=y+dy[k];
		if(a[tx][ty]==1 && v[tx][ty]==0)//如果(是空地 并且 没有被访问) 
			{
			v[tx][ty]=1;//设置为已访问 
			dfs(tx,ty,step+1);
			v[tx][ty]=0;
			}
	}
	return;
}

下面为完整代码

#include<cstdio>
using namespace std;
int m,n,p,q,min=99999999;//p,q是终点坐标 
int a[100][100];//地图 ,其中1表示空地，2表示障碍物 
int v[100][100]; //0表示未访问，1表示已访问 
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0}; 
 
void dfs(int x,int y,int step){
	if(x==p && y==q)
	{
		if(step<min)	
		min=step;
		return;//回溯 
	}
	for(int k=0;k<=3;k++)
	{
		int tx,ty;
		tx=x+dx[k];
		ty=y+dy[k];
		if(a[tx][ty]==1 && v[tx][ty]==0)//如果(是空地 并且 没有被访问) 
			{
			v[tx][ty]=1;//设置为已访问 
			dfs(tx,ty,step+1);
			v[tx][ty]=0;
			}
	}
	return;
}

int main()
{
	int startx,starty; 
	printf("请输入地图的行与列:\n"); 
	scanf("%d%d",&m,&n);
	printf("请输入地图障碍物布局:\n");1表示空地，2表示障碍物
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		scanf("%d",&a[i][j]);//1表示空地，2表示障碍物
	printf("请输入起点坐标和终点坐标:\n");	
	scanf("%d%d%d%d",&startx,&starty,&p,&q);
	v[startx][starty]=1;
	dfs(startx,starty,0);
	printf("需要%d步",min);
	
	return 0;
	
}

运行结果如下图所示

dfs迷宫问题,深度优先,算法,图论