PKU : 3036 - Honeycomb Walk
アルゴリズム
dp[14(残りのステップ数)][100(x座標)][100(y座標)] = スタートまで行けるパターン数
のDPを行えばいい.
プログラム
スタート地点を(0,0)とすると, 配列の外へアクセスしてしまうため, (20,20)からスタートしています.
int dp[20][100][100]; int dx[] = {-1,1,0, 0,-1,1}; int dy[] = { 0,0,1,-1,-1,1}; int dfs(int rem,int x,int y){ if(rem == 0){ if(x == 20 && y == 20) return 1; return 0; } if(dp[rem][x][y] != -1) return dp[rem][x][y]; int res = 0; rep(i,6){ res += dfs(rem-1,x+dx[i],y+dy[i]); } return dp[rem][x][y] = res; } int main(void){ int T; scanf("%d",&T); memset(dp,-1,sizeof(dp)); while(T--){ int n; scanf("%d",&n); printf("%d\n",dfs(n,20,20)); } }