A bee larva living in a hexagonal cell of a large honey comb decides to creep for a walk. In each “step” the larva may move into any of the six adjacent cells and after n steps, it is to end up in its original cell. Your program has to compute, for a given n, the number of different such larva walks.
The ?rst line contains an integer giving the number of test cases to follow. Each case consists of one line containing an integer n, where 1 ≤ n ≤ 14. SAMPLE INPUT 2 2 4
For each test case, output one line containing the number of walks. Under the assumption 1 ≤ n ≤ 14, the answer will be less than 2^31. SAMPLE OUTPUT 6 90
dp
/* *********************************************** Author :guanjun Created Time :2016/10/5 13:32:45 File Name :spojMBEEWALK.cpp ************************************************ */ #include <bits/stdc++.h> #define ull unsigned long long #define ll long long #define mod 90001 #define INF 0x3f3f3f3f #define maxn 10010 #define cle(a) memset(a,0,sizeof(a)) const ull inf = 1LL << 61; const double eps=1e-5; using namespace std; priority_queue<int,vector<int>,greater<int> >pq; struct Node{ int x,y; }; struct cmp{ bool operator()(Node a,Node b){ if(a.x==b.x) return a.y> b.y; return a.x>b.x; } }; bool cmp(int a,int b){ return a>b; } ll dp[50][50][50]; //第i步 到达位置 j k的方案数 int dir[6][2]={ 1,0,-1,0,0,1,0,-1,1,-1,-1,1 }; void init(){ cle(dp); dp[0][15][15]=1; for(int i=1;i<=15;i++){ for(int x=1;x<=30;x++){ for(int y=1;y<=30;y++){ for(int j=0;j<6;j++){ int nx=x+dir[j][0]; int ny=y+dir[j][1]; dp[i][x][y]+=dp[i-1][nx][ny]; } } } } } int main() { #ifndef ONLINE_JUDGE //freopen("in.txt","r",stdin); #endif //freopen("out.txt","w",stdout); int t,n; init(); cin>>t; while(t--){ cin>>n; if(n==1)puts("0"); else{ cout<<dp[n][15][15]<<endl; } } return 0; }
A bee larva living in a hexagonal cell of a large honey comb decides to creep for a walk. In each “step” the larva may move into any of the six adjacent cells and after n steps, it is to end up in its original cell. Your program has to compute, for a given n, the number of different such larva walks.
The ?rst line contains an integer giving the number of test cases to follow. Each case consists of one line containing an integer n, where 1 ≤ n ≤ 14. SAMPLE INPUT 2 2 4
For each test case, output one line containing the number of walks. Under the assumption 1 ≤ n ≤ 14, the answer will be less than 2^31. SAMPLE OUTPUT 6 90
原文：http://www.cnblogs.com/pk28/p/5932279.html