路径计数
题目 路径计数
思路分析
路径数 dfs吗
起点0,0 终点0,0
写的时候发现一个问题
0,0点一开始被标记了已走过 导致到不了终点 可是如果不标记走过的话 就可能一直走回头路
需要一种解决措施 使得0,0位置在走的时候不会被重复走 且最后还能回到0,0处 ？
或者换个思路 从1,0处和0,1处作为起点 找它们到终点0,0的路径数 最后减去2（1，0直接到0,0 相当于0,0->1,0->0,1实际非法 0,1直接到0,0同理） 或者直接找1,0和0,1为起点 到0,0的 路径长度大于2的所有方案数
最后注意 因为是从0,1 和 1,0开始的 默认是已经从0,0走到了这两个位置 所以step一开始为1
很多细节这题 又是填空 一不小心就会错
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=10;
int cnt=0;
bool st[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=4 && y>=0 && y<=4 && !st[x][y];
}
void dfs(int x,int y,int step){
if(step>12) return;
if(x==0 && y==0 && step > 2){
cnt++;
return;
}
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(isVaild(nx,ny)){
st[nx][ny]=true;
dfs(nx,ny,step+1);
st[nx][ny]=false;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
st[1][0]=true;
dfs(1,0,1);
st[1][0]=false;
st[0][1]=true;
dfs(0,1,1);
st[0][1]=false;
cout<<cnt;
return 0;
}
💬 评论