解题思路:
n不超过20,先写一个dfs爆搜。
因为是二维数组,所以把只能向上、左、右走改成了向下、左、右走,起始位置在(0,50),这样向下左右走不会超过边界。
先将起始位置标记为-1,表示不能返回。
以走三步为例,所有可能走过的位置如图所示:
参考代码:
#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分
154 人评分
拆分位数 (C语言代码)浏览:1325 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:1419 |
简单的a+b (C语言代码)浏览:596 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:1294 |
C语言程序设计教程(第三版)课后习题8.2 (C语言代码)浏览:5227 |
2005年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:582 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:664 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:668 |
图形输出 (C语言代码)浏览:1375 |
1071题解浏览:484 |