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

一、问题引入

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

 

二、问题的分析

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

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

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

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

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

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

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

这道题可以有两种解法，一种是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;	
}