P1605 迷宫 题解

在进入正题之前，我们先来看一个题目 迷宫由n行m列的单元格组成（n,m都小于等于100），每个单元格要么是空地（1），要么是障碍物（0）你的任务是帮助小哼找到一条从迷宫的起点通往小哈所在位置的最少步数。 输入:第一行，n,m 第2~n+1行 每行m个数（0或1） 第n+2行:sx（起点横坐标），sy（起点纵坐标），fx（终点横坐标），fy（终点纵坐标） 输出:1个数，为最少步数（保证有解） 代码: ``` #include<bits/stdc++.h>//万能头 using namespace std; int n,mi=0,m; int dx[4]={0,0,1,-1};//4方向 int dy[4]={1,-1,0,0}; int nex[101][101];//判断是否走过数组 int tem[101][101];//地图数组 int fx,fy,sx,sy; void dfs(int x,int y,int ste) { if(x==fx&&y==fy) { mi=ste;//换成全局变量输出 return ; } for(int i=0;i<=3;i++) { if(nex[x+dx[i]][y+dy[i]]==0&&tem[x+dx[i]][y+dy[i]]==1)//如果没有走过且没障碍 { nex[x][y]=1;//标记过已走过 dfs(x+dx[i],y+dy[i],ste+1);//继续搜索 nex[x][y]=0;//回溯一步 } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>tem[i][j]; nex[i][j]=0;//全标记为没走过 } } cin>>sx>>sy>>fx>>fy; dfs(sx,sy,0); cout<<mi; return 0; } 好 如果你上面这题会写 那么本题（P1605）你也会写了 只需要在代码上做点修改，如下: #include<bits/stdc++.h>//万能头 using namespace std; int n,m,coun=0,t; int sx,sy,fx,fy; int ma[6][6]; int a[6][6]={0};//全为没走过 int dx[4]={0,0,1,-1};//地图数组 int dy[4]={1,-1,0,0}; int b,c;//障碍坐标 void dfs(int x,int y) { if(x==fx&&y==fy)//如果到达 { coun++;return ;//方案+1并回溯 } else{ for(int i=0;i<=3;i++) { if(ma[x+dx[i]][y+dy[i]]==1&&a[x+dx[i]][y+dy[i]]==0)//如果没有障碍且没有走过 { a[x][y]=1;//标记为已走过 dfs(x+dx[i],y+dy[i]);//继续搜索 a[x][y]=0;//回溯一步 } } } } int main() { cin>>n>>m>>t; cin>>sx>>sy>>fx>>fy; a[sx][sy]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { ma[i][j]=1;//全标记为空地 } } for(int i=1;i<=t;i++) { cin>>b>>c; ma[b][c]=0;//标记障碍 } dfs(sx,sy);//开始搜索 printf("%d",coun); return 0; } 做完这道题后，大家也可以做一下P1451 P1506 P1596 都是DFS求联通块的题目 最后，希望大家能学会DFS，也希望管理大大能通过此篇题解！