読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 11611 : Colored Tiles

UVa 動的計画法

問題リンク:http://uva.onlinejudge.org/external/116/11611.html

問題概要:
H*Wのマスに図にあるようなピースを置いていく
マスは3種類あり、
空のマスにはピースを置ける
壊れているマスにはピースを置けない
色の指定があるマスにはその色のピースしかおけない
ピースを回転させて置いてはいけない
ピースの置き方は何通りあるか?

解法:
1行覚えるDP
dp[1行+2の状態][2] := 現在の状態のピースの置き方の総数
あるマスにピースを置く際に必要な情報はそのマスから左の行と上の行とそのマスの左斜め上
一般化するために+2マス追加
見ているマスのx座標が端まできたら、遷移が特殊になるので注意

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int MOD = 50431,LIMIT = (1<<11);

int H,W,dp[LIMIT][2],piece[] = {14,3,6,7,3,6,2};
char G[20][20], TYPE[] = {'R','G','B','N','W','P','L'};

bool isValid(int x,int y) { return 0 <= x && x < W && 0 <= y && y < H; }

bool match(char c,int type){ return ( c == TYPE[type] || c == '.' ); }

bool can_put(int x,int y,int bitmask,int type){

  if( type == 0 ) {
    if( !isValid(x,y-1) || !isValid(x+1,y-1) ) return false;
    if( !( match(G[y][x],type) && match(G[y-1][x],type) && match(G[y-1][x+1],type) ) ) return false;
    if( ( (bitmask>>(x+2)) & 1 ) || ( (bitmask>>(x+3)) & 1 ) ) return false;
  } else if( type == 1 ) {
    if( y-1 < 0 || x-1 < 0 ) return false;
    if( !( match(G[y][x],type) && match(G[y][x-1],type) && match(G[y-1][x-1],type) ) ) return false;
    if( ( (bitmask>>(x+1)) & 1 ) || ( (bitmask>>x) & 1 ) ) return false;
  } else if( type == 2 ) {
    if( y-1 < 0 || x-1 < 0 ) return false;
    if( !( match(G[y][x],type) && match(G[y-1][x],type) && match(G[y-1][x-1],type) ) ) return false;
    if( ( (bitmask>>(x+1)) & 1 ) || ( (bitmask>>(x+2)) & 1 ) ) return false;

  } else if( type == 3 ) {
    if( y-1 < 0 || x-1 < 0 ) return false;
    if( !( match(G[y][x],type) && match(G[y][x-1],type) && match(G[y-1][x],type) ) ) return false;
    if( ( (bitmask>>x) & 1 ) || ( (bitmask>>(x+2)) & 1 ) ) return false;
  } else if( type == 4 ) {
    if( x-1 < 0 ) return false;
    if( !( match(G[y][x],type) && match(G[y][x-1],type) ) ) return false;
    if( ( (bitmask>>(x)) & 1 ) ) return false;
  } else if( type == 5 ) {
    if( y-1 < 0 ) return false;
    if( !( match(G[y][x],type) && match(G[y-1][x],type) ) ) return false;
    if( ( bitmask>>(x+2) ) & 1 ) return false;
  } else if( type == 6 ) {
    if( !match(G[y][x],type) ) return false;
  } 
  return true;
}

int main(){
  int T,CNT=1;
  scanf("%d",&T);
  while(T--){
    cout << "Case " << CNT++ << ": ";
    scanf("%d%d",&W,&H);
    rep(i,W)rep(j,H) scanf(" %c",&G[j][W-1-i]);

    rep(i,(1<<(W+2))) dp[i][0] = 0;
    dp[0][0] = 1;

    rep(y,H)rep(x,W){
      int phase = ( x + y * W ) & 1;
      rep(i,(1<<(W+2))) dp[i][!phase] = 0;
      rep(bitmask,(1<<(W+2))){
        // dont put
        bool no_bit = false, no_bit2 = false;
        if( isValid(x-1,y-1) && G[y-1][x-1] != '#' && !( ( bitmask >> (x+1) ) & 1 ) ) no_bit = true;
        if( x == W-1 && isValid(x,y-1) && G[y-1][x] != '#' && !( ( bitmask >> (x+2) ) & 1 ) ) no_bit2 = true;
        int nbitmask = bitmask & ~(1<<(x+1));
        if( x == W-1 ) ( nbitmask <<= 1 ) &= ((1<<(W+2))-1);
        if( !no_bit && !no_bit2 ) ( dp[nbitmask][!phase] += dp[bitmask][phase] ) %= MOD;

        // put
        rep(type,7){
          if( !can_put(x,y,bitmask,type) ) continue;
          if( no_bit  && !( type == 1 || type == 2 ) ) continue;
          if( no_bit2 && ( type == 1 || type == 4 || type == 6 ) ) continue;
          nbitmask = bitmask | (piece[type]<<x);
          if( x == W-1 ) ( nbitmask <<= 1 ) &= ((1<<(W+2))-1);
          ( dp[nbitmask][!phase] += dp[bitmask][phase] ) %= MOD;
        }
      }
    }

    int mask = 0;
    rep(i,W) if( G[H-1][i] != '#' ) mask |= (1<<i);
    mask <<= 2;
    cout << dp[mask][(H*W)&1] << endl;
  }
  return 0;
}