P1605 迷宫 题解（dfs 深度优先搜索）
发布时间
阅读量：
阅读量
P1605 迷宫
- 题目
- 分析
- 代码
- 传送门
题目
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
输入格式
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。
输出格式
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。
输入输出样例
输入
2 2 1
1 1 2 2
1 2输出
1【数据规模】
1≤N,M≤5
分析
非常简单的一道迷宫题，用一个数组去记录经过的路径，障碍物可以当作已经走过的路，剩下的就是基本的dfs模板了，具体细节请看代码注释哦~
代码
//1605
#include<iostream>
using namespace std;
typedef struct{
int x,y;
}Site;
int n,m,t;
Site s,f;
int a[30][30];
int d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}} ;
int ans;
void dfs(Site ss){
if(ss.x == f.x && ss.y == f.y){ //到达终点方案数增加
ans++;
return;
}
for(int i = 0;i< 4;i++){ //每一个点有4个方向，即4种选择
Site sss = ss; //下一个节点坐标
sss.x += d[i][0];
sss.y += d[i][1];
if(sss.x <= 0 || sss.x > n || sss.y <= 0 || sss.y > m || a[sss.x][sss.y]){ // 边界判定及路径判定
continue;
}else {
a[sss.x][sss.y] = 1;
dfs(sss);
a[sss.x][sss.y] = 0; //恢复状态
}
}
}
int main(){
cin>>n>>m>>t;
cin>>s.x>>s.y>>f.x>>f.y;
for(int i = 0;i < t;i++){
Site b;
cin>>b.x>>b.y;
a[b.x][b.y] = 1;
}
a[s.x][s.y] = 1; //起点只能走一次
dfs(s);
cout<<ans<<endl;
return 0;
}传送门
全部评论 (0)
还没有任何评论哟~