PKU 3036 Honeycomb Walk
http://poj.org/problem?id=3036
ハニカム構造で、隣り合う場所に移動することをn回繰り返すとき、スタートと最終到達地点が同じ場所になるような移動方法は何通りあるかを答える問題。
動的計画法。i回の移動のあとに、x,yに到達するパターンを記録しておく。
ハニカム構造は水平のx軸と、x軸に対して60度の角度のy軸を考えた。
int dp[15][50][50]; int tx[]={-1,0,1,1,0,-1},ty[]={1,1,0,-1,-1,0}; main(){ dp[0][25][25]=1; for(int i=1;i<15;i++){ for(int x=5;x<45;x++){ for(int y=5;y<45;y++){ rep(k,6)dp[i][x+tx[k]][y+ty[k]]+=dp[i-1][x][y]; } } } int n; cin>>n; while(n--){ int t; cin>>t; cout<<dp[t][25][25]<<endl; } }