迷宫问题----深搜经典问题
程序员文章站
2022-05-20 20:49:27
...
迷宫问题是深搜算法的最常见也是最基础的题型之一
深搜大家应该都已经理解了
如果还不知道深搜是什么可以参考我之前的一篇:深搜讲解
我们把我们撞南墙才回头的思想运用到我们的迷宫问题中
就可以理解为:
从起点开始随便找一条路开始走
走到了终点或没有继续向前的格子就回头
用最简单的2x2迷宫来举例
如果我们设起点是(1,1)这个点,终点是(2,2)这个点,
障碍物是(2,1)这个点。
我们从起点开始可以选择去(1,2)或者去(2,1),但后者是障碍物,所以我们只能选择(1,2),到了这个点我们可以只能去(2,2)(因为走过的地方不能再走),所以我们到达了终点,此时我们回头去寻找另外的路径。但我们发现,不管退到前面的哪一步(包括退回到起点),我们都没有其他的路径选择,所以最后的答案就只有一条。
(如果没有理解,建议先把上一篇讲解深搜的先理解透彻)。
接下来我们直接看code
点击查看题目>>来自洛谷
#include <bits/stdc++.h>
using namespace std;
int n,m,t;
int a[10][10]; //标记x,y这个点是否是障碍物或已经被走过
int nowi,nowj;//现在走到哪里了,即现在的坐标
int toi,toj;//终点坐标
int flag;//有几种路径,即最后输出的答案
void work(int x);//运行函数
int main()
{
while(cin >> n >>m >> t)
{
flag=0;
cin >> nowi >> nowj >> toi >> toj;
a[nowi][nowj]=1;//对起点进行标记
for(int i=1; i<=t; i++)
{
int x,y;
cin >> x >> y;
a[x][y]=1;//给障碍物进行标记
}
work(1);
cout << flag << endl ;
a[nowi][nowj]=0;//清楚此次起点的标记
memset(a,0,sizeof(a));//最后清0数组,具体是清楚障碍物标记的地方
}
return 0;
}
void work(int x)
{
if(nowi==toi&&nowj==toj)
//达到了终点,flag++,并且不再进行函数的其他操作,其实可以++完直接return
{
flag++;
}
else
{//这里的x为1,2,3,4的操作可以根据自己喜好来调换
if(x==1)//把它移动向行数增加的那一格
{
if(a[nowi+1][nowj]==0&&nowi+1<=n)
{
a[nowi+1][nowj]=1;//标记这个位置
nowi++;
work(1);
nowi--;
a[nowi+1][nowj]=0;//别忘记这里要清楚标记
}//如果不懂这种if函数为什么这样写,可以先理解上一篇的代码,有详细讲解
}
if(x==2)//把它移动向列数增加的那一格
{
if(a[nowi][nowj+1]==0&&nowj+1<=m)
{
a[nowi][nowj+1]=1;
nowj++;
work(1);
nowj--;
a[nowi][nowj+1]=0;
}
}
if(x==3)//把它移动向行数减少的那一格
{
if(a[nowi-1][nowj]==0&&nowi-1>=1)
{
a[nowi-1][nowj]=1;
nowi--;
work(1);
nowi++;
a[nowi-1][nowj]=0;
}
}
if(x==4)//把它移动向列数减少的那一格
{
if(a[nowi][nowj-1]==0&&nowj-1>=1)
{
a[nowi][nowj-1]=1;
nowj--;
work(1);
nowj++;
a[nowi][nowj-1]=0;
}
}
if(x+1<=4)//不能加else哦,理解一下
/*不管是不满足以上条件,还是从上面条件运行完再出来,
都要进行它的下一项(如果没有超出边界的话)*/
work(x+1);
}
}
推荐阅读
-
Java实现的求解经典罗马数字和阿拉伯数字相互转换问题示例
-
目标关键词排名还没上来时 网站的热搜关键词问题解答
-
Python使用random和tertools模块解一些经典概率问题
-
Java实现的求解经典罗马数字和阿拉伯数字相互转换问题示例
-
C#用递归算法解决经典背包问题
-
Python解决走迷宫问题算法示例
-
海外VPS主机选购的15条常见问题经典总结
-
经典问题(c++/python)素数、杨辉三角(金字塔型)、统计单词数、简单计算器、密码安全程度、凯撒密码加密、汉诺塔 (python课设实验实例)-- biaobiao88
-
深大云网络在H5开发中解决IE浏览器的兼容问题
-
搜推宝软件使用问题汇总 搜推宝设置指南