描述
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设： a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上； b. 走过的格子立即塌陷无法再走第二次； c. 只能向北、东、西三个方向走； 请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
输入 允许在方格上行走的步数n(n <= 20) 输出 计算出的方案数量 样例输入 2 样例输出 7思路：
此题直觉觉得是规律题，然后慢慢写出了几种情况，f[0]=1,f[1]=3,f[2]=7,f[3]=17;然后发现了规律即f[i]=f[i-1]*2+f[i-1],然后便试了一下，结果就AC了，此题还可以使用递归的方法，f(int n,int x,int y),n步数在不断减小，如果路过则将值置为1,否则为0如果n=0,则返回1,否则 num+=fun(n-1,i+dx[r],j+dy[r]);注意，每次一组数据完以后，都要将数据全置为0!
代码：
#include <iostream> using namespace std; int main() { int n,f[22],i; f[0]=1; f[1]=3; f[2]=7; f[3]=17; for(i=4;i<22;i++) { f[i]=2*f[i-1]+f[i-2]; } while(cin>>n) { cout<<f[n]<<endl; } return 0; }代码2：
#include<bits/stdc++.h> using namespace std; int a[32][62]; int dx[]={1,0,0}; int dy[]={0,1,-1}; int fun(int n,int x,int y) { if(n==0) return 1; int num=0; a[x][y]=1; for(int k=0;k<3;k++) { if(a[x+dx[k]][y+dy[k]]==0) num+=fun(n-1,x+dx[k],y+dy[k]); } a[x][y]=0; return num; } int main() { int n,i,x,y; x=0; y=32; a[x][y]=1; cin>>n; int s=fun(n,x,y); cout<<s<<endl; return 0; } 心得：
规律的发现是一个漫长复杂的过程，只要规律发现，代码就非常简单！
