Window Pains

题解：如果i窗口挡在j窗口的前面，则在i，j之间建一条有向边，这样建图，建成有向图，然后就是判断是否有环，如果有环，就是否，否则就是yes。用一遍拓扑排序即可。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 int map[5][5];//存储原来的图 
 7 int g[10][10];//储存窗口之间的边图 
 8 int counts[10];//记录每个点的入度    
 9 char str[30];
10 //build是以i，j为左上角的起点来判断周围4个点之间的关系，如果不相同则建边 
11 void build(int i,int j,int goal){
12     if(map[i][j]!=goal&&!g[map[i][j]][goal])
13      {g[map[i][j]][goal]=1;
14        counts[goal]++;}
15        if(map[i][j+1]!=goal&&!g[map[i][j+1]][goal])
16      {g[map[i][j+1]][goal]=1;
17        counts[goal]++;}
18        if(map[i+1][j]!=goal&&!g[map[i+1][j]][goal])
19      {g[map[i+1][j]][goal]=1;
20        counts[goal]++;}
21        if(map[i+1][j+1]!=goal&&!g[map[i+1][j+1]][goal])
22      {g[map[i+1][j+1]][goal]=1;
23        counts[goal]++;}
24 }
25 bool Topsort(){//拓扑排序判断是否有环 
26     int cnt,pos;
27     for(int i=1;i<=9;i++){
28         cnt=0;
29         for(int j=1;j<=9;j++){
30             if(counts[j]==0){
31                 pos=j;cnt++;
32             }
33         }
34         counts[pos]=-1;
35         if(cnt==0)return false;
36         for(int k=1;k<=9;k++){
37             if(g[pos][k]==1){
38                 counts[k]--;
39             }
40         }
41     }
42     return true;    
43 }
44 int main(){
45     while(~scanf("%s",str)){
46         if(!strcmp("ENDOFINPUT",str))break;
47         memset(counts,0,sizeof(counts));
48         memset(map,0,sizeof(map));
49         memset(g,0,sizeof(g));
50         for(int i=1;i<=4;i++)
51           for(int j=1;j<=4;j++)
52             cin>>map[i][j];
53             scanf("%s",str);
54             int k=0;
55         for(int i=1;i<=3;i++)
56           for(int j=1;j<=3;j++){
57               k++;
58             build(i,j,k);}
59   if(Topsort())printf("THESE WINDOWS ARE CLEAN
");
60          else
61          printf("THESE WINDOWS ARE BROKEN
") ; 
62            
63     }
64 }

View Code