[走迷宫上瘾]关于迷宫问题与深搜的爱恨情仇_洛谷b3936

千万不要一看标题就觉得我们今天是来玩游戏的，只是因为深搜算法的题目，十道里有七道都是关于迷宫的。（请计算概率）

告诉大家深搜（dfs）和广搜(bfs)的区别：

深搜是一条路干到底，广搜是多点开花（通俗易懂）

 不废话了上题目吧

 一：OpenJudge   2.5基本算法之搜索----2753走迷宫

OpenJudge - 2753:走迷宫

这题刚AC，代码还热乎着呢（这又什么神奇脑回路！）

AC代码：

#include<iostream>
using namespace std;
int r,c,a[105][105],minn=10000000000,sum=1,x,y;
char  b[105][105];
void fun(int x,int y)
{
	if(x==r&&y==c)
	{
		if(sum<minn)
		{
			minn=sum;
		}
		return;
	}
	if(b[x][y]==0||a[x][y]==1||b[x][y]=='#')
	{
		return;
	}
	else
	{
		a[x][y]=1;
		sum++;
		fun(x+1,y);
		fun(x,y+1);
		fun(x-1,y);
		fun(x,y-1); 
		a[x][y]=0;
		sum--;
	}
	return; 
}
int main()
{
	int i,j;
	cin>>r>>c;
	for(i=1;i<=r;i++)
	{
		for(j=1;j<=c;j++)
		{
			cin>>b[i][j];
		}
	}
	fun(1,1);
	cout<<minn;
	return 0;
}

说实话OpenJudge里还有一道题可以拿深搜做，TA就是

OpenJudge - 1700:八皇后问题

啊没错就是八皇后。 

题解我已经写过了，大家可以查看：题解之八皇后问题-CSDN博客

  

二：洛谷B3625 迷宫寻路

迷宫寻路 - 洛谷

这题很基础但很重要

核心代码：

#include<iostream>
using namespace std;
int x,y,n,m,d[105][105];  //定义所需数组变量 
char o[105][105];
void fun(int x,int y)  //直接输出用void 
{
    if(x==n&&y==m)  //是否到达终点 
    {
        cout<<"Yes";   //成功的输出 
        exit(0);   //结束全部 
    }
    if(o[x][y]=='#'||o[x][y]==0||d[x][y]==1)   
     //失败的情况 ：o[x][y]=='#'是当前是墙壁，o[x][y]==0是越界，d[x][y]==1是已经走过了被标记了 
    {
        return;  //返回上一层 
    }
    else
    {
        d[x][y]=1;   //标记已经走过了 
        //四个方向搜索 
        fun(x+1,y);
        fun(x,y+1);
        fun(x-1,y);
        fun(x,y-1);
    }
    return;   //返回上一层 
}
int main()
{
    int i,j;   //不在函数中使用就在主函数里定义 
    //输入 
    cin>>n>>m;  
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>o[i][j];
        }
    }
    fun(1,1);  //使用函数 
    cout<<"No";  //失败的输出
    return 0;  //结束 
}

AC代码：

#include<iostream>
using namespace std;
int x,y,n,m,d[105][105]; 
char o[105][105];
void fun(int x,int y) 
{
	if(x==n&&y==m) 
	{
		cout<<"Yes"; 
		exit(0); 
	}
	if(o[x][y]=='#'||o[x][y]==0||d[x][y]==1)   
	{
		return; 
	}
	else
	{
		d[x][y]=1; 
		fun(x+1,y);
		fun(x,y+1);
		fun(x-1,y);
		fun(x,y-1);
	}
	return; 
}
int main()
{
	int i,j; 
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>o[i][j];
		}
	}
	fun(1,1); 
	cout<<"No"; 
	return 0; 
}

这段代码理解透彻做其他迷宫问题就比较容易了。 

三：洛谷P1605 迷宫

迷宫 - 洛谷

AC代码

#include<iostream>
using namespace std;
int sx,sy,fx,fy,n,m,t,l[105][105],i,j,d[105][105],sum;
char o[105][105];
void fun(int x,int y)
{
	if(x==fx&&y==fy)
	{
		sum++;
		return;
	}
	if(o[x][y]==0||o[x][y]=='*'||d[x][y]==1)
	{
		return;
	}
	else
	{
		d[x][y]=1;
		fun(x,y+1);
		fun(x+1,y);
		fun(x,y-1);
		fun(x-1,y);
		d[x][y]=0;
	}
	return;
}
int main()
{
	int k,r,e;
	cin>>n>>m>>t;
	cin>>sx>>sy>>fx>>fy;
	for(i=1;i<=t;i++)
	{
		cin>>e>>r;
		o[e][r]='*'; 
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(o[i][j]!='*')
			{
				o[i][j]='!';
			}
		}
	}
	if(o[fx][fy]=='*')
	{
		cout<<0;
		return 0;
	}
	fun(sx,sy);
	cout<<sum;
	return 0;
}

先转化成char类型的迷宫再做。 

接下来两道题的题目在这个网站查看：

青少年软件编程（C语言五级）等级考试真题试卷（2022年6月） | 考级竞赛题库

四，逃离迷宫 

AC代码

#include<iostream>
using namespace std;
int t,m,k,x,y,minute,f[105][105],flag; 
char a[105][105];
void fun(int x,int y)
{
	if(a[x][y]=='E'&&minute<=t)
	{
			flag=1;
			return;
	}
	if(a[x][y]==0||a[x][y]=='#'||minute>t||f[x][y]==1)
	{
		return;
	}
	else
	{
		f[x][y]=1;
		minute++;
		fun(x+1,y);
		fun(x,y+1);
		fun(x-1,y);
		fun(x,y-1);
		f[x][y]=0;
		minute--;
	}
}
int main()
{
	int i,j,qx,qy;
	cin>>k;
	while(k--)
	{
		flag=0;
		cin>>m>>t;
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=m;j++)
			{
				cin>>a[i][j];
				if(a[i][j]=='S')
				{
					qx=i;
					qy=j;
				}
			}
		}
		fun(qx,qy);
		if(flag==1)
		{
			cout<<"YES"<<endl;
		}
		else
		{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}

五，夺宝探险

AC代码

#include<iostream>
using namespace std;
int a[105][105],f[105],x,y,t,maxx;
int m,n,k,sum=0;
void fun(int x,int y)
{
	t=a[x][y];
	int q,w;
	if(a[x][y]==0||f[a[x][y]]==1)
	{
		maxx=max(maxx,sum);
	}
	else
	{
		f[a[x][y]]=1;
		sum++;
		fun(x+1,y);
		fun(x,y+1);
		fun(x-1,y);
		fun(x,y-1);
		f[a[x][y]]=0;
		sum--;
	}
}
int main()
{
	int i,j,o;
	cin>>m>>n>>k;
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	fun(1,1);
	cout<<maxx;
}

可以用桶排的思想去做。

总结

 判断失败与成功的情况，标记，朝几个方向搜索，还原现场。

就按这个思路来，肯定没问题。

结束！

祝大家学算法都能听懂，写代码都能AC。