数据结构之图论之深搜广搜

ゞ浴缸里的玫瑰 2022-05-12 09:04 240阅读 0赞

## 一、问题引入 ##

有一天，小哈一个人去玩迷宫。但是方向感不好的小哈很快就迷路了。小哼得知后便去解救无助的小哈。此时的小哼已经弄清楚了迷宫的地图，现在小哼要以最快的速度去解救小哈。那么，问题来了...

![922928-20170825191830355-501498782.png][]

## 二、问题的分析 ##

首先我们用一个二维数组来存储这个迷宫，刚开始的时候，小哼处于迷宫的入口处（1,1），小哈在（p,q）。其实这道题的的本质就在于找从（1,1）到（p,q）的最短路径。

此时摆在小哼面前的路有两条，我们可以先让小哼往右边走，直到走不通的时候再回到这里，再去尝试另外一个方向。

在这里我们规定一个顺序，按照顺时针的方向来尝试（即右→下→左→上）。

![922928-20170825195542152-1662666496.png][]

我们先来看看小哼一步之内可以到达的点有哪些？只有（1,2）和（2,1）。

根据刚才的策略，我们先往右边走，但右边（1,3）有障碍物，所以只能往下（2,2）这个点走。但是小哈并不在（2,2）这个点上，所以小哼还得继续往下走，直至无路可走或者找到小哈为止。

注意：并不是让我们找到小哈此题就解决了。因为刚才只是尝试了一条路的走法，而这条路并不一定是最短的。刚才很多地方在选择方向的时候都有多种选择，因此我们需要返回到这些地方继续尝试往别的方向走，直到把所有可能都尝试一遍，最后输出最短的一条路径。

例如下图就是一条可行的搜索路径：

![922928-20170825200422339-125974986.png][]

这道题可以有两种解法，一种是dfs，一种是bfs。粘贴代码，首先是dfs：

20分钟hou :::::         自己代码找不到了，分分钟手写一个：

//广度优先搜索解救小哈 
    //众所周知：深搜用栈广搜用队列。 
    #include<bits/stdc++.h>
    using namespace std;
    
    int a[51][51],v[51][51],m,n,p,q,minn=9999;
    int next[4][2]={
       {0,1},{1,0},{0,-1},{-1,0}};
    void dfs(int tx,int ty,int step)
    {
    	if(tx==p&&ty==q){
    		if(step<minn)minn=step;
    		return ;
    	}
    
    	for(int i=0;i<4;i++){
    		int x,y;
    		x=tx+next[i][0];
    		y=ty+next[i][1];
    		if(x<1||y<1||x>n||y>m)continue;
    		if(a[x][y]==0&&v[x][y]==0){
    			v[x][y]=1;
    			dfs(x,y,step+1);
    			v[x][y]=0;
    		}
    	}
    }
    int main()
    {
    	cin>>n>>m;
    	for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++)
    			cin>>a[i][j];
    	cin>>p>>q;
    	v[1][1]=1;
    	dfs(1,1,0);
    	cout<<minn;
    	return 0;
    }

下面是广搜的解法：

广度优先搜索解救小哈 
    众所周知：深搜用栈广搜用队列。 
    #include<cstdio>
    #include<cmath>
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    int a[51][51]={},n,m,v[51][51]={},p,q;//迷宫，状态数组，初始化 
    struct que{
    	int x;
    	int y;
    	int step;
    }queue[2505];//手写队列 
    int main()
    {
    	int head=1,tail=2,x,y;
    	cin>>m>>n;
    	for(int i=1;i<=n;i++)
    		for(int j=0;j<=m;j++)
    			cin>>a[i][j];//输入迷宫，障碍物输入1，其他为0； 
    	a[1][1]=1;
    	v[1][1]=1;
    	queue[1].x=1;
    	queue[1].y=1;
    	queue[1].step=0;//第一个入队 
    	int next[4][2]={
       {0,1},{1,0},{0,-1},{-1,0}};//能够遍力四个方面 
    	bool flag=false;
    	while(head<tail)
    	{	
    		for(int i=0;i<4;i++){
    			x=queue[head].x+next[i][0];
    			y=queue[head].y+next[i][1];
    			if(x<1||y<1||x>n||y>m)continue;//判断是否越界 
    			if((a[x][y]==0)&&(v[x][y]==0)){//判断是否可行 
    				v[x][y]=1; //标记 
    				queue[tail].x=x;
    				queue[tail].y=y;
    				queue[tail].step=queue[head].step+1;
    				tail++;//队尾加1 
    			}
    			if(x==p&&y==q){
    				flag=true;
    				break;
    			}//得到结果 
    		}
    		if(flag)break;//退出循环 
    		head++;//该点已经遍历完毕，出队 
    	}
    	cout<<queue[--tail].step;//打印！ 
    	return 0;	
    }

[922928-20170825191830355-501498782.png]: /images/20220512/cc29dedb336941f6a097debd762174f0.png
[922928-20170825195542152-1662666496.png]: /images/20220512/65b999ade27042718fef68926b0c1b54.png
[922928-20170825200422339-125974986.png]: /images/20220512/178fa3f8793849d2ae99507776fc6218.png