首页 > 代码库 > MBEEWALK - Bee Walk
MBEEWALK - Bee Walk
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 cellsand 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.
Input
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 INPUT224
Output
For each test case, output one line containing the number of walks. Under theassumption 1 ≤ n ≤ 14, the answer will be less than 2^31.SAMPLE OUTPUT690
dp
/* ***********************************************Author :guanjunCreated Time :2016/10/5 13:32:45File 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 cellsand 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.
Input
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 INPUT224
Output
For each test case, output one line containing the number of walks. Under theassumption 1 ≤ n ≤ 14, the answer will be less than 2^31.SAMPLE OUTPUT690
MBEEWALK - Bee Walk
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。