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 阅读(168) 评论(0)  编辑 收藏 引用 所属分类: graph


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年10月>
日一二三四五六
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜