AOJ 2297 - Rectangular Stamps

問題概要

4×4の紙があり、最初この紙には色は塗られていない。今、N個のスタンプを持っていて、各スタンプの大きさはそれぞれH_i×W_iである。紙にスタンプを押すと押された部分が全てそのスタンプの色に変わる(既にスタンプが押されていたら更新される)。スタンプの色は赤・緑・青の好きな色を選ぶことができる。また、スタンプは紙から一部がはみ出た状態でも押すことが可能である。このとき4×4の紙に指定された赤・緑・青の通りの絵を完成させるための最小のスタンプを押す回数を求めよ。

制約

• 1 ≤ N ≤ 16
• 1 ≤ H_i ≤ 4
• 1 ≤ W_i ≤ 4
• (H_i , W_i)の同一の組は複数現れない

解法

状態としてbitを持ち、bfsする。
bitは、完成した絵と色が一致している部分に1を立てる。

感想

ループがやたらと多くなったのでちょっと見にくくなったのが残念…。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1e9
typedef pair<int,int> pii;
 
int N,C[4][4];
pii stamp[16];
 
inline int stp(int x,int y,int px,int py,int c,int S){
  for(int i = max(0,py) ; i < min(py+y,4) ; i++){
    for(int j = max(0,px) ; j < min(px+x,4) ; j++){
      int b = i*4+j;
      if(C[i][j] == c){
        if((S >> b) & 1) continue;
        S |= (1<<b);
      }else{
        if((S >> b) & 1){
          S -= (1<<b);
        }
      }
    }
  }
  return S;
}
 
int solve(){
  queue<int> Q;
  Q.push(0);
  int dist[1<<16];
  fill(dist,dist+(1<<16),INF);
  dist[0] = 0;
 
  while(!Q.empty()){
    int S = Q.front(); Q.pop();
    if(S == (1<<16)-1){
      return dist[S];
    }
    for(int i = 0 ; i < N ; i++){
      pii p = stamp[i];
      int x = p.second, y = p.first;
      for(int j = 0 ; j < 3 ; j++){
        for(int px = -x+1 ; px < 4 ; px++){
          for(int py = -y+1 ; py < 4 ; py++){
            int nS = stp(x,y,px,py,j,S);
            if(dist[S]+1 < dist[nS]){
              dist[nS] = dist[S] + 1;
              Q.push(nS);
            }
          }
        }
      }
    }
  }
  return -1;
}
 
int change(char ch){
  if(ch == 'R') return 0;
  if(ch == 'B') return 1;
  return 2;
}
 
int main(){
  cin >> N;
  for(int i = 0 ; i < N ; i++){
    cin >> stamp[i].first >> stamp[i].second;
  }
  char in;
  for(int i = 0 ; i < 4 ; i++){
    for(int j = 0 ; j < 4 ; j++){
      cin >> in;
      C[i][j] = change(in);
    }   
  }
  cout << solve() << endl;
  return 0;
}