首页 > 代码库 > POJ 2585 Window Pains 拓扑排序

POJ 2585 Window Pains 拓扑排序

 

 

 

  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 START113 1 2 3 3114 4 5 6 6115 7 8 9 9116 7 8 9 9117 END118 START119 1 1 3 3120 4 1 3 3121 7 7 9 9122 7 7 9 9123 END124 ENDOFINPUT125 126 */

 

POJ 2585 Window Pains 拓扑排序