POJ 1691 - Painting A Board

http://poj.org/problem?id=1691

概要

ある長方形が \(N\) 枚の長方形の板に分割されており，\(i\) 番目の板は色 \(c_i\) で塗らなければならない．

ある板の色を塗る前に，その板の真上にある板は既に塗られていなければならない． また板を部分的に塗ることはできない．

異なる色で塗るときは別の筆に取り替えなければならない． すべての板を塗るのに必要な筆を取る回数の最小値を答える． 最初の板を塗るときに筆を取る必要があるので，最小値は1以上であることに注意．

制約

• \(1 \le N \le 15\)
• \(1 \le c_i \le 20\)
• \(0 \le \mbox{座標} \le 99\)

解法

\(N\) が小さいので普通に DFS で探索しても大丈夫． 各板について，その板の真上にあって塗られていない板の数 \(d_i\) を保持し， \(d_i = 0\) の板について再帰的に色を塗ってみて最小値をとる．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 struct rect
 6 {
 7   int c, y1, x1, y2, x2;
 8   bool above(const rect& r) const
 9   {
10     return y2 == r.y1 && (
11         (x1 <= r.x2 && r.x2 <= x2)
12         || (x1 <= r.x1 && r.x1 <= x2)
13         );
14   }
15 };
16 
17 int dfs(const vector<rect>& v, const vector<vector<int> >& g, vector<int>& deg, int color, unsigned done)
18 {
19   const int N = v.size();
20   if (done == (1<<N)-1) {
21     return 0;
22   } else {
23     int ans = 100;
24     for (int i = 0; i < N; i++) {
25       if (!(done & (1<<i)) && deg[i] == 0) {
26 
27         for (vector<int>::const_iterator it = g[i].begin(); it != g[i].end(); ++it) {
28           --deg[*it];
29         }
30         const int a = dfs(v, g, deg, v[i].c, done | (1<<i));
31         ans = min(ans, (color != v[i].c) + a);
32         for (vector<int>::const_iterator it = g[i].begin(); it != g[i].end(); ++it) {
33           ++deg[*it];
34         }
35       }
36     }
37     return ans;
38   }
39 }
40 
41 int main()
42 {
43   int T;
44   cin >> T;
45   while (T-- > 0) {
46     int N;
47     cin >> N;
48     vector<rect> v(N);
49     vector<int> deg(N, 0);
50     vector<vector<int> > g(N);
51     for (int i = 0; i < N; i++) {
52       cin >> v[i].y1 >> v[i].x1 >> v[i].y2 >> v[i].x2 >> v[i].c;
53       for (int j = 0; j < i; j++) {
54         if (v[i].above(v[j])) {
55           g[i].push_back(j);
56           ++deg[j];
57         } else if (v[j].above(v[i])) {
58           g[j].push_back(i);
59           ++deg[i];
60         }
61       }
62     }
63     int ans = 100;
64     for (int i = 0; i < N; i++) {
65       if (deg[i] == 0) {
66         for (vector<int>::const_iterator it = g[i].begin(); it != g[i].end(); ++it) {
67           --deg[*it];
68         }
69         ans = min(ans, 1 + dfs(v, g, deg, v[i].c, 1<<i));
70         for (vector<int>::const_iterator it = g[i].begin(); it != g[i].end(); ++it) {
71           ++deg[*it];
72         }
73       }
74     }
75     cout << ans << endl;
76   }
77   return 0;
78 }