AOJ 2297 - Rectangular Stamps

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2297

解法

各マスが「正しい色」で塗られているかそうでないかで状態を持つと，状態数は 2^16 程度しかないので，これで BFS する．

あるスタンプで塗ることができる領域を予め計算しておくと，実装も楽だし高速化もできる．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N;
 9   cin >> N;
10   static bool drawable[4][4][4][4];
11   for (int i = 0; i < N; i++) {
12     int H, W;
13     cin >> H >> W;
14     for (int k = -H+1; k < 4; k++) {
15       for (int l = -W+1; l < 4; l++) {
16         drawable[max(0, k)][max(0, l)][min(3, k+H-1)][min(3, l+W-1)] = true;
17       }
18     }
19   }
20   vector<string> goal(4);
21   for (int i = 0; i < 4; i++) {
22     cin >> goal[i];
23   }
24 
25   queue<int> q;
26   q.push(0);
27   static const int INF = 1000000;
28   vector<int> dist(1<<16, INF);
29   dist[0] = 0;
30   while (!q.empty()) {
31     const int n = q.front();
32     q.pop();
33     if (n == (1<<16)-1) {
34       break;
35     }
36     for (int i = 0; i < 4; i++) {
37       for (int j = 0; j < 4; j++) {
38         for (int k = i; k < 4; k++) {
39           for (int l = j; l < 4; l++) {
40             if (drawable[i][j][k][l]) {
41               for (int c = 0; c < 3; c++) {
42                 static const char rgb[] = "RGB";
43                 const char cc = rgb[c];
44                 int next = n;
45                 for (int x = i; x <= k; x++) {
46                   for (int y = j; y <= l; y++) {
47                     if (goal[x][y] == cc) {
48                       next |= 1 << (4*x+y);
49                     } else {
50                       next &= ~(1 << (4*x+y));
51                     }
52                   }
53                 }
54                 if (dist[n]+1 < dist[next]) {
55                   dist[next] = dist[n]+1;
56                   q.push(next);
57                 }
58               }
59             }
60           }
61         }
62       }
63     }
64   }
65   cout << dist[(1<<16)-1] << endl;
66   return 0;
67 }