總時間限制: 1000ms 內存限制: 65536kB
描述
有一個方格矩陣，矩陣邊界在無窮遠處。我們做如下假設：
a. ? ?每走一步時，只能從當前方格移動一格，走到某個相鄰的方格上；
b. ? ?走過的格子立即塌陷無法再走第二次；
c. ? ?只能向北、東、西三個方向走；
請問：如果允許在方格矩陣上走n步，共有多少種不同的方案。2種走法只要有一步不一樣，即被認為是不同的方案。


輸入
允許在方格上行走的步數n(n <= 20)
輸出
計算出的方案數量
樣例輸入
2
樣例輸出

7

分析

使用遞歸的方法，將方向分開處理，從（i，j）出發，等于三個方向的步數和；

代碼：

#include <iostream>
#include <cstring>
using namespace std;
int visited[30][50];
int ways(int i,int j,int n)
{if(n==0)return 1;visited[i][j] = 1;int num = 0;if(! visited[i][j-1])num+=ways(i,j-1,n-1);if(! visited[i][j+1])num+=ways(i,j+1,n-1);if(! visited[i+1][j])num+=ways(i+1,j,n-1);visited[i][j] = 0;return num;
}int main()
{int n;cin>>n;memset(visited, 0 ,sizeof(visited));cout <<ways(0,25,n)<<endl;return 0;
}