16:踩方格

描述 有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设： a.    每走一步时，只能从当前方格移动一格，走到某个相邻的方格上； b.    走过的格子立即塌陷无法再走第二次； c.    只能向北、东、西三个方向走； 请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。

输入

允许在方格上行走的步数n(n <= 20) 输出 计算出的方案数量 样例输入 2 样例输出

7

解题思路：

对于从（i,j）开始的第n步，等于在其北，东，西三个点开始走的n-1步，条件是点没走过，

细节处理：

出发点在列中间，对于多种情况下可能用到同一点，所以在每种情况递归完，进行下一情况时，要将当前点初始化

代码：

#include<iostream> using namespace std; int a[30][60]; int dx[3]={1,0,0}; int dy[3]={0,1,-1}; int fun(int n,int i,int j) { if(n==0) return 1; int num=0; a[i][j]=1; for(int r=0;r<3;r++) { if(a[i+dx[r]][j+dy[r]]==0) num+=fun(n-1,i+dx[r],j+dy[r]); } a[i][j]=0; return num; } int main() { int n,i,x,y; x=0; y=30; a[x][y]=1; cin>>n; int t=fun(n,x,y); cout<<t; return 0; }