问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1691思路:
首先要解决的问题是如何合理地表示整个Board?
这题还是在青岛洲际无聊的时候用手机看到的，当时想到用一颗树的父子节点来表示各个矩形之间的上下关系
其实，这是一个有向图，而表示的方法则可以很简单地使用二维数组(因为矩形的个数比较少)进行标记即可
另一个巧妙之处是记录每个节点的入度，当入度为零时表示可以Painting
在用有向图进行表示之后，剩下的就是搜索了(太菜，参考人家的)
代码:
1 int
2 solve(int last_color, int count)
3 {
4 int i, j, rt;
5 int ans = 1000000;
6 for(i=0; i<n; i++) {
7 if(!visited[i] && degree[i]==0) {
8 visited[i] = 1;
9 if(recs[i].color != last_color)
10 ++count;
11 for(j=0; j<n; j++)
12 if(graph[i][j])
13 --degree[j];
14 rt = solve(recs[i].color, count);
15 ans = rt<ans ? rt : ans;
16 visited[i] = 0;
17 if(recs[i].color != last_color)
18 --count;
19 for(j=0; j<n; j++)
20 if(graph[i][j])
21 ++degree[j];
22 }
23 }
24 if(ans == 1000000)
25 ans = count;
26 return ans;
27 }
1 void
2 build_graph()
3 {
4 int i, j;
5 for(i=0; i<n; i++)
6 for(j=0; j<n; j++)
7 if(i!=j && is_immdt_above(recs+i, recs+j)) {
8 graph[i][j] = 1;
9 ++degree[j];
10 }
11 }
1 /* if rec1 is immediate above rec2, return 1 */
2 int
3 is_immdt_above(struct Rec *rec1, struct Rec *rec2)
4 {
5 if(rec1->lwrgt_x==rec2->uplft_x && !(rec1->lwrgt_y<=rec2->uplft_y || rec1->uplft_y>=rec2->lwrgt_y))
6 return 1;
7 return 0;
8 }