P1605 迷宫 的题解
huangkx
2019-10-04 21:28:59
### 这是一道深度优先搜索的题,还是比较简单的,那本蒟蒻就来写一篇题解吧
### (我可不会告诉别人我不会BFS的)逃~
------------
#### 先说说我的思路:
初始化:首先全部初始化为障碍(就是0),再把n行全部初始化为1,最后把障碍点变为0
接着来个大爆搜:先判断a == ex && b == ey,如果是就ans++;return;否则就判断上下左右,然后回溯
输出:输出ans就搞定了
深度优先搜索大家应该都懂吧,那就直接上代码了
```cpp
#include<iostream>
#include<cstring>
using namespace std;
int mp[101][101];//迷宫
int ans = 0;//记录答案数量
int n,m,t,sx,sy,ex,ey,x,y;
void dfs(int a,int b)//搜索
{
if (a==ex&&b==ey){ans++; return;}//判断是否到达终点
mp[a][b] = 0;
if(mp[a-1][b] != 0){dfs(a-1,b); mp[a-1][b] = 1;}
if(mp[a][b-1] != 0){dfs(a,b-1); mp[a][b-1] = 1;}
if(mp[a][b+1] != 0){dfs(a,b+1); mp[a][b+1] = 1;}
if(mp[a+1][b] != 0){dfs(a+1,b); mp[a+1][b] = 1;}//这四句是判断上下左右
}
int main()
{
memset(mp,0,sizeof(mp));//初始化为0
cin>>n>>m>>t;
cin>>sx>>sy>>ex>>ey;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp[i][j] = 1;//在初始化为1
for(int i=1;i<=t;i++){cin>>x>>y; mp[x][y] = 0;}//标出障碍
dfs(sx,sy);//调用
cout<<ans<<endl;//输出
return 0;
}
```