当前位置：首页 > news >正文

POJ 2585 Window Pains 拓扑排序

news 来源：原创 2024/5/19 17:29:44

题意：

给了你9种图片问给的图片能不能由这九种构成

思路：

拓扑排序对能存在的点连边

如果不存在环的话这个图就成立否则不成立

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #define cl(a,b) memset(a,b,sizeof(a))
  5 using namespace std;
  6 
  7 const int maxn=10;
  8 
  9 int T;
 10 int cnt[maxn];
 11 int mp[maxn][maxn];
 12 int num[maxn][maxn];
 13 int cover[maxn][maxn][maxn];
 14 bool vis[maxn];
 15 bool link[maxn][maxn];
 16 
 17 int dx[]= {0,0,1,1};
 18 int dy[]= {0,1,0,1};
 19 
 20 void init()
 21 {
 22     int i,j;
 23     cl(cover,0);
 24     for(int k=0; k<9; k++)
 25     {
 26         i=k/3,j=k%3;
 27         for(int l=0; l<4; l++)
 28         {
 29             int x=i+dx[l];
 30             int y=j+dy[l];
 31             cover[x][y][num[x][y]++]=k+1;
 32         }
 33     }
 34 }
 35 
 36 void build()
 37 {
 38     for(int i=0; i<4; i++)
 39     {
 40         for(int j=0; j<4; j++)
 41         {
 42             for(int k=0; k<num[i][j]; k++)
 43             {
 44                 if((!link[mp[i][j]][cover[i][j][k]])
 45                  &&(mp[i][j]!=cover[i][j][k]))
 46                 {
 47                     link[mp[i][j]][cover[i][j][k]]=true;
 48                     cnt[cover[i][j][k]]++;
 49                 }
 50             }
 51         }
 52     }
 53 }
 54 
 55 bool topsort()
 56 {
 57     while(T--)
 58     {
 59 
 60         int now=1;
 61         while(!vis[now]||(now<=9&&cnt[now]>0))
 62         {
 63             now++;
 64 //            printf("%d\n",now);
 65         }
 66 
 67         if(now>9)
 68         {
 69             return false;
 70         }
 71         vis[now]=false;
 72         for(int i=1; i<=9; i++)
 73         {
 74             if(vis[i]&&link[now][i])
 75             {
 76                 cnt[i]--;
 77             }
 78         }
 79     }
 80     return true;
 81 }
 82 
 83 int main()
 84 {
 85     init();
 86     char str[maxn];
 87     while(scanf("%s",str)&&str[0]=='S')
 88     {
 89         cl(cnt,0),T=0;
 90         cl(vis,false);
 91         cl(link,false);
 92         for(int i=0; i<4; i++)
 93         {
 94             for(int j=0; j<4; j++)
 95             {
 96                 scanf("%d",&mp[i][j]);
 97                 if(!vis[mp[i][j]])
 98                 {
 99                     T++;
100                     vis[mp[i][j]]=true;
101                 }
102             }
103         }
104         build();
105         scanf("%s",str);
106         if(topsort()) puts("THESE WINDOWS ARE CLEAN");
107         else puts("THESE WINDOWS ARE BROKEN");
108     }
109     return 0;
110 }/*
111 
112 START
113 1 2 3 3
114 4 5 6 6
115 7 8 9 9
116 7 8 9 9
117 END
118 START
119 1 1 3 3
120 4 1 3 3
121 7 7 9 9
122 7 7 9 9
123 END
124 ENDOFINPUT
125 
126 */