首页 > 代码库 > 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 拓扑排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。