PKU : 3036 - Honeycomb Walk

問題概要

http://poj.org/problem?id=3036

Hex座標のある座標からスタートして, Nステップ後にスタート地点に戻ってくるようなパターン数が何通りあるか答えよ.

アルゴリズム

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));
  }
}