首页 > 代码库 > 4982:踩方格
4982:踩方格
4982:踩方格
- 查看
- 提交
- 统计
- 提问
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:
a. 每走一步时,只能从当前方格移动一格,走到某个相邻的方格上;
b. 走过的格子立即塌陷无法再走第二次;
c. 只能向北、东、西三个方向走;
请问:如果允许在方格矩阵上走n步,共有多少种不同的方案。2种走法只要有一步不一样,即被认为是不同的方案。 - 输入
- 允许在方格上行走的步数n(n <= 20)
- 输出
- 计算出的方案数量
- 样例输入
-
2
- 样例输出
-
7
很好理解的题,递推即可;1 #include<bits/stdc++.h> 2 using namespace std; 3 int up[10000], r[10000], lef[10000], total[100000]; 4 int main() 5 { 6 int n; 7 cin >> n; 8 up[1] = 1; r[1] = 1; lef[1] = 1; 9 for(int i=2;i<=n*n+1;i++) 10 { 11 r[i] = up[i - 1] + r[i - 1]; 12 lef[i] = up[i - 1] + lef[i - 1]; 13 up[i] = up[i - 1] + lef[i - 1] + r[i - 1]; 14 total[i] = r[i] + lef[i] + up[i]; 15 } 16 cout << total[n] << endl; 17 return 0; 18 }
4982:踩方格
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。