AOJ : 2297 - Rectangular Stamps

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2297
日本語の問題文なので, 説明は省略です.

アルゴリズム

マップが4＊4なので, 16ビットの2進数の状態にすることができます.
各ビットが, １のときは目的の色に塗れていることを表し, ０のときは目的の色に塗れていないことを表すように, 状態を管理しましょう.

あとは, 全ての塗り方を試すように, 幅優先で遷移していけば解くことができます.

やらかしたミス

• マップの大きさが t[4][4] になってた. ヌル文字も考えて, [5][5]にしておく必要があった.
• BFSの遷移のとき, 六重ループで書いてたらTLE. 明らかに内側の二重ループは, 前処理しておくべきだった.

プログラム

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

typedef pair<int,int> P;

int n;
int h[16],w[16];
int b[16][3][8][8],b2[16][3][8][8];
bool closed[1<<16];
char t[10][10],ch[]="RGB";

void solve(){
  queue<P> open;
  memset(closed,0,sizeof(closed));
  open.push(P(0,0));
  closed[0] = true;

  while(!open.empty()){
    P p = open.front(); open.pop();

    if(p.second == (1<<16)-1){
      printf("%d\n",p.first);
      return;
    }

    //以下, BFSの遷移

    rep(k,n){ //どのスタンプを使うか
      rep(color,3){ //どの色で塗るか
        REP(si,-h[k]+1,4){ //開始行
          REP(sj,-w[k]+1,4){ //開始列
            int bit = p.second;
            bit |= b[k][color][si+4][sj+4];
            bit -= (bit & b2[k][color][si+4][sj+4]);

            if(!closed[bit]){
              closed[bit] = true;
              open.push(P(p.first+1,bit));
            }
          }
        }
      }
    }
  }
}

int main(void){
  while(scanf("%d",&n) != EOF){
    rep(i,n){
      scanf("%d%d",&h[i],&w[i]);
    }

    rep(i,4){
      scanf("%s",t[i]);
    }

    //スタンプで色を塗るとき用の前処理
    rep(k,n){
      rep(color,3){
        REP(si,-h[k]+1,4){
          REP(sj,-w[k]+1,4){
            int bit = 0;
            int bit2 = 0;

            REP(i,si,si+h[k]){
              REP(j,sj,sj+w[k]){
                if(i < 0 || j < 0 || 4 <= i || 4 <= j) continue;

                int tmpBit = (1<<(i*4+j));
                if(t[i][j] == ch[color]){
                  bit |= tmpBit;
                }
                else{
                  bit2 |= tmpBit;
                }
              }
            }

            b[k][color][si+4][sj+4] = bit;
            b2[k][color][si+4][sj+4] = bit2;
          }
        }
      }
    }

    solve();
  }
}