問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1691思路:
首先要解決的問題是如何合理地表示整個(gè)Board?
這題還是在青島洲際無聊的時(shí)候用手機(jī)看到的，當(dāng)時(shí)想到用一顆樹的父子節(jié)點(diǎn)來表示各個(gè)矩形之間的上下關(guān)系
其實(shí)，這是一個(gè)有向圖，而表示的方法則可以很簡(jiǎn)單地使用二維數(shù)組(因?yàn)榫匦蔚膫€(gè)數(shù)比較少)進(jìn)行標(biāo)記即可
另一個(gè)巧妙之處是記錄每個(gè)節(jié)點(diǎn)的入度，當(dāng)入度為零時(shí)表示可以Painting
在用有向圖進(jìn)行表示之后，剩下的就是搜索了(太菜，參考人家的)
代碼:
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 }