指针原来是套娃的


私信TA

用户名:uq_92467646842

访问量:39903

签 名:

数学改变科学,科学改变世界

等  级
排  名 10
经  验 24520
参赛次数 49
文章发表 124
年  龄 0
在职情况 学生
学  校
专  业 物联网工程

  自我简介:

QQ:2830671713

解题思路:
n不超过20,先写一个dfs爆搜。

因为是二维数组,所以把只能向上、左、右走改成了向下、左、右走,起始位置在(0,50),这样向下左右走不会超过边界。

先将起始位置标记为-1,表示不能返回。

以走三步为例,所有可能走过的位置如图所示:

image.png

参考代码:

#include <iostream>
using namespace std;

int dx[3]={1,0,0};//下 左 右
int dy[3]={0,-1,1};
int dp[107][107];
int n,z;
void dfs(int x1,int y1,int k) {
	if(k==n){//走了n步,计数+1 
		z++;
		return;
	}
	for(int i=0; i<3; i++) {//三个方向 
		int x=x1+dx[i],y=y1+dy[i];
		if(dp[x][y]!=-1) {//如果没有走过 
			dp[x][y]=-1;//标记为走过 
			dfs(x,y,k+1);//向下一方向搜索 
			dp[x][y]=1;//因为要回溯,所以重新标记为没有走过 
		}
	}
}

int main() {
	cin>>n;
	dp[0][50]=-1;//起始点标记为-1 
	dfs(0,50,0);
	cout<<z<<endl;
	//打印查看 
//	for(int i=0; i<5; i++) {
//		for(int j=45; j<55; j++)cout<<dp[i][j]<<" \n"[j==54];
//	}

	return 0;
}


 

0.0分

1 人评分

  评论区