DFS深度优先算法解决迷宫问题

2021-10-25 22:19:29

文章目录

前言

>>今天遇到了一个需要使用dfs算法的题，无奈对dfs一知半解，只好在网上找了帖子学习，然后写下这篇文章进行记录，以便日后复习回顾。

先写出可以求解出结果的程序，然后进行改进。

一、问题描述

示例：迷宫由n行m列的单元格组成（n，m都小于等于50）每个单元格要么是空地，要么是障碍物。
现请你找到一条从起点到终点的最短路径长度。

二、解决步骤

1.分析

思想就是能向某个方向走下去就一直向那个方向走，不能走再切换方向，所有方向都不能走了就回到上一层位置。注意边界。

2.第一遍程序

	先写出一个可以运行出正解的程序

代码如下：

#include<iostream>

using namespace std;

int m,n;
// 终点
int p,q;
int minstep=9999;
// 1表示空地，2表示障碍物
int a[100][100]={0};

//0表示未访问，1表示访问
int v[100][100]={0};

void dfs(int x,int y,int step){
    //终点
    if(x==p&&y==q){
        if(step<minstep){
            minstep = 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-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-1][y-1]==1&&v[x-1][y-1]==0){
        v[x-1][y-1] = 1;
        
        dfs(x-1,y-1,step+1);
        v[x-1][y-1]=0;
    }
    return ;
}

int main(){
    int starx,stary;
    freopen("file in.txt","r",stdin);
    cin>>m>>n>>starx>>stary>>p>>q;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }    
    v[starx][stary] = 1;
    dfs(starx,stary,0);
    cout<<minstep;
}

3.对程序进行改进

	查找规律，用for循环替代上面的循环；
	输出可能的路径方案

代码如下：


/* 对上面的四个选择进行改进*/
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<iostream>
using namespace std;
// 用循环改进四个选择 坐标变换规律，坐标变换后符合右，下，左，上
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
// 先把最小路径设成一个比较大的数
int  minstep=99999999;
// 存储迷宫的数组
int maze[100][100]={0};
// 记录迷宫的每一个位置是否被访问
int visit[100][100]={0};
// 迷宫行列，开始点坐标 ，结束点（需要到达）坐标
int  rows,column,startx,starty,endx,endy;
// 每次路径经过的点进行保存
struct node{
	int x;
	int y;
};
struct node s[100];
// 路径点个数
int top=0;


// 路线方案
int route=0;


void dfs(int x,int y,int step)
{   
    // 到达终点
	if(x==endx && y==endy)
	{
		route++;
		cout<<"第"<<route<<"组方案："<<endl; 
		if(step< minstep)
			 minstep=step;
        // 输出路线
		for(int i=0;i<=top;i++)
		{
			cout<<s[i].x<<","<<s[i].y<<"-->";
		}
        cout<<"finished"<<endl<<endl;
		
		return;
	}
    // 还没到达终点
	for(int k=0;k<4;k++)
	{
		int tx=x+dir[k][0];
		int ty=y+dir[k][1];
		
        // 边界处理
		if(tx<1||tx> rows||ty<1||ty>column)
			continue;
        // 不是障碍物，且没有被访问过
		if(maze[tx][ty]==1 && visit[tx][ty]==0)
		{
			visit[tx][ty]=1;
			top++;
			s[top].x = tx;
			s[top].y = ty;
			
            // 每一层里面step都不一样
			dfs(tx,ty,step+1);
            // 回退时把这个点又设为为访问，以便下一条路径可以重复访问这个点
			visit[tx][ty]=0;
			top--;
		}
	}
}
int main()
{   
    //freopen("file in.txt","r",stdin);
	cin>>rows>>column>>startx>>starty>>endx>>endy;
	
	
	
	for(int i=1;i<=rows;i++)
		for(int j=1;j<=column;j++)
			cin>>maze[i][j];
			
	visit[startx][starty]=1;
	s[0].x = startx;
	s[0].y = starty;
	
	dfs(startx,starty,0);\
    cout<<endl;
	cout<< minstep;
	return 0;

}

4.file in.txt记事本里面的内容

5 4
1 1 4 3
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2

来源： https://search.bilibili.com/all?keyword=dfs

总结

1. 使用递归方式求解：先判断当前点是否为终点，非终点时递归调用DFS
2. 调用DFS前当前点标记为已访问，DFS执行结束后当前点标记为未访问：前者防止递归调用时重复访问当前点走回头路，后者是为探索其他路径时能重复访问该点。
3. 使用外部变量统计最小步数

码农公寓