P1958 上学路线 题解
_Vistion_
·
·
题解
P1958 上学路线
考虑用 DFS 解开。
核心变量
int a,b;
int vis[M][M];
int n;
int X,Y;
int nxt[5][3]={{1,0},{0,1}};
int tot;
$vis$ 表示走过的路的记录。
$N$ 表示有 $N$ 个路口在维修。
$X$，$Y$ 表示路口位置。
```
int nxt[5][3]={{1,0},{0,1}};
```
方向数组，代表东和北。
$tot$用来记录路径条数。
#### 深搜代码
注意事项：
> 走过的路不能走
>
> 不能走到施工区域
>
> 不能越界
---
接着就可以按照思路写下以下代码。
```
void dfs(int x,int y)
{
if(x==a&&y==b){
tot++;
return;
}
for(int i=0; i<2; i++){
int nx=nxt[i][0]+x,ny=nxt[i][1]+y;
if(vis[nx][ny]||nx<1||nx>a||ny<1||ny>b) continue;
else{
vis[nx][ny]=1;
dfs(nx,ny);
vis[nx][ny]=0;
}
}
}
```
---
#### 主函数部分代码
```
cin>>a>>b>>n;
while(n--){
cin>>X>>Y;
vis[X][Y]=1;
}
vis[1][1]=1;
dfs(1,1);
cout<<tot;
```
输入，标记，输出。
---
#### 完整代码（带注释）
```
#include <bits/stdc++.h>
#define int long long
#define ll ((i)*2)
#define rr ((i)*2+1)
using namespace std;
const int M=1e2+10;
const int mod=1e9+7;
int a,b; //表示有 a 条南北方向的街道和 b 条东西方向的街道
int vis[M][M]; //标记数组，标记走过的路或者施工路口
int n; //表示有 N 个路口在维修
int X,Y; //表示路口位置
int nxt[5][3]={{1,0},{0,1}}; //方向数组
int tot; //路径条数
void dfs(int x,int y) // x 坐标，y 坐标
{
if(x==a&&y==b){ //当 (x,y) == (a,b)，路径条数 +1 , return
tot++;
return;
}
for(int i=0; i<2; i++){ //两个方向
int nx=nxt[i][0]+x,ny=nxt[i][1]+y; //下一个位置
if(vis[nx][ny]||nx<1||nx>a||ny<1||ny>b) continue; //如果走过（包含施工路口），越界。则跳出第 i 次循环
else{ //否则
vis[nx][ny]=1; //标记
dfs(nx,ny); //dfs~~
vis[nx][ny]=0; //标记还原
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>a>>b>>n; //输入
while(n--){
cin>>X>>Y; //输入路口位置
vis[X][Y]=1; //标记为 1
}
vis[1][1]=1; //第一个位置一定要标记！！！
dfs(1,1); //dfs~~
cout<<tot; //输出路径条数
return 0;
}
```