PKU : 2663 - Tri Tiling

問題概要

http://poj.org/problem?id=2663
3*nの枠に, 1*2 or 2*1のタイルを使って, ぴったり埋める方法は何通りあるでしょう.
ただし, n=0のときは, 答えは1です.

アルゴリズム

メモ化再帰で解きました.
他の人のブログを見てみると, すごくかしこい方針で解いているのに対して, 僕の方針はあまりかしこくないかもです.

[3][n]の枠があるとき, 以下のように左上から順番に単純再帰して考えていきました.
[0][0]→[1][0]→[2][0]→[0][1]→...

あとは, メモ化する方法です.
[i][j]以降のパターン数を求めるためには, j列目とj+1列目の状態（6つの場所がタイルで埋まっているか否か）がわかってさえいれば, 確定させることができます.
なので, 次のようなメモ用配列を作ってメモ化しました.

• dp[3][31][2^6]

他の人は, O(n)で解けてるみたいなので, そっちの方法を検索してもらった方がいいかもです.

プログラム

int n;
int dp[4][32][64];
bool t[4][32];

int dfs(int x,int y){
  //インデックスが下に飛び出したら右上へ補正
  if(y == 3){
    x++;
    y = 0;
  }

  //右端までいけば再帰終了
  if(x == n){
    if(t[0][n-1] && t[1][n-1] && t[2][n-1]) return 1;
    return 0;
  }

  //x列目とx+1列目の状態をビット化する
  int bit = 0;
  rep(i,3){
    REP(j,x,x+2){
      bit <<= 1;
      bit += t[i][j];
    }
  }
  if(dp[y][x][bit] != -1) return dp[y][x][bit];

  int res = 0;

  //今の場所がタイルで埋まっているとき
  if(t[y][x]){
    res = dfs(x,y+1);
  }
  //今の場所がタイルで埋まっていないとき
  else{
    //横置き
    if(x < n-1){
      t[y][x] = t[y][x+1] = true;
      res += dfs(x,y+1);
      t[y][x] = t[y][x+1] = false;
    }
    //縦置き
    if(y < 2 && !t[y+1][x]){
      t[y][x] = t[y+1][x] = true;
      res += dfs(x,y+1);
      t[y][x] = t[y+1][x] = false;
    }
  }

  return dp[y][x][bit] = res;
}

int main(void){
  while(cin>>n,n!=-1){
    if(n == 0){
      cout<<"1\n";
      continue;
    }
    if(n % 2 == 1){
      cout<<"0\n";
      continue;
    }

    memset(t,0,sizeof(t));
    memset(dp,-1,sizeof(dp));
    cout<<dfs(0,0)<<endl;
  }
}