PKU3853 Painting 拓撲排序

題意大概是這樣，有一個n*n的棋盤，每次可以將棋盤的一行或者一列染成一種顏色，現在給出棋盤的末狀態，請給出一種染色的方案，并且要求字典序最小

Summary

可以使用類似拓撲排序的方法處理這個問題。對于每種顏色，有三種可能：可以判斷橫放，可以判斷豎放，不可判斷。之后不斷選出一個在最上面顏色，刪去（也就是設置為0）。判斷最上面的要求是：該顏色在該行的數目，加上已經被刪去（也就是0）的方格，等于列的數目；或該顏色在該列的數目，加上已經被刪去（也就是0）的方格，等于行的數目。

注意字典序的處理。因為我們是逆序得到答案的。拓撲排序中，要逆序得到字典序最大，才能得到正序的字典序最小

 1# include <iostream>
 2# include <set>
 3# include <stack>
 4using namespace std;
 5int map[101][101];
 6int n,m;
 7bool selectrow(int pos,int num)
 8{
 9   for(int i=0;i<m;i++)
10     if(map[pos][i]!=-1&&map[pos][i]!=num) return false;
11   for(int i=0;i<n;i++)
12       if(i!=pos)
13           for(int j=0;j<m;j++)
14               if(map[i][j]==num)
15                   return false;
16   return true;
17}
18bool selectcol(int pos,int num)
19{
20   for(int i=0;i<n;i++)
21     if(map[i][pos]!=-1&&map[i][pos]!=num) return false;
22   for(int j=0;j<m;j++)
23       if(j!=pos)
24           for(int i=0;i<n;i++)
25               if(map[i][j]==num)
26                   return false;
27   return true;
28}
29int main()
30{
31    while(true)
32    {
33       cin>>n>>m;
34       set<int,greater<int> > refer;
35       if(!n&&!m) break;
36       for(int i=0;i<n;i++)
37         for(int j=0;j<m;j++)
38         {
39           cin>>map[i][j];
40           refer.insert(map[i][j]);
41         }
42       
43       stack<int> ans;
44       while(!refer.empty())
45       {
46         // if(emptymap()) break;
47          for(set<int,greater<int> >::iterator p=refer.begin();p!=refer.end();p++)
48          {
49             for(int i=0;i<n;i++)
50               for(int j=0;j<m;j++)
51                  if(map[i][j]==(*p))
52                  {
53                     if(selectrow(i,*p))
54                     {
55                       for(int k=0;k<m;k++)
56                       {
57                          map[i][k]=-1;
58                       }
59                       ans.push(*p);
60                       refer.erase(p);
61                       goto end;
62                     }
63                     else if(selectcol(j,*p))
64                     {
65                       for(int k=0;k<n;k++)
66                         map[k][j]=-1;
67                       ans.push(*p);
68                       refer.erase(p);
69                       goto end;
70                     }
71                  }
72          }
73          end:;
74       }
75       while(!refer.empty())
76       {
77          ans.push(*refer.begin());
78          refer.erase(refer.begin());
79       }
80       cout<<ans.top();
81       ans.pop();
82       while(!ans.empty())
83       {
84         cout<<" "<<ans.top();
85         ans.pop();
86       }
87       cout<<endl;
88    }
89    return 0;
90}
91
92

posted on 2010-10-14 19:19 yzhw 閱讀(177) 評論(0)  編輯 收藏 引用 所屬分類: graph