P1605 迷宫 的题解

huangkx

2019-10-04 21:28:59

Solution

### 这是一道深度优先搜索的题,还是比较简单的,那本蒟蒻就来写一篇题解吧 ### (我可不会告诉别人我不会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; } ```