【POJ 2585】Window Pains 拓扑排序

Description

. . . and so on . . .
Unfortunately, Boudreaux's computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly. And this is where you come in . . .

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 3 components:

Start line - A single line:
START
Screen Shot - Four lines that represent the current graphical representation of the windows on Boudreaux's screen. Each position in this 4 x 4 matrix will represent the current piece of window showing in each square. To make input easier, the list of numbers on each line will be delimited by a single space.
End line - A single line:
END

After the last data set, there will be a single line:
ENDOFINPUT

Note that each piece of visible window will appear only in screen areas where the window could appear when brought to the front. For instance, a 1 can only appear in the top left quadrant.

Output

For each data set, there will be exactly one line of output. If there exists a sequence of bringing windows to the foreground that would result in the graphical representation of the windows on Boudreaux's screen, the output will be a single line with the statement:

THESE WINDOWS ARE CLEAN

Otherwise, the output will be a single line with the statement:
THESE WINDOWS ARE BROKEN

Sample Input

START
1 2 3 3
4 5 6 6
7 8 9 9
7 8 9 9
END
START
1 1 3 3
4 1 3 3
7 7 9 9
7 7 9 9
END
ENDOFINPUT

Sample Output

THESE WINDOWS ARE CLEAN
THESE WINDOWS ARE BROKEN
-----------------------------------------------------------------------------
最早想到的是dfs 从最上面一层倒着往回推，但最后没法记录点了.....

其实就是个拓扑排序的水题.....
主要是建边：枚举9个炮台，如果在自己射程区域内不是自己，说明被覆盖，因此说明这个颜色是当前颜色的先决条件，
于是连一条边。（开始理解为只要不是自己就连边，结果根本没有入度为0的边23333
然后跑一遍拓扑排序，如果没成环就成功了，成环就失败。
这是代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<queue>
 6 #include<vector>
 7 #define N 20
 8 using namespace std;
 9 struct node
10 {
11     int u,v,nxt;
12 }e[N*2];
13 int first[N],cnt;
14 void ade(int u,int v)
15 {
16     e[++cnt].nxt=first[u]; first[u]=cnt;
17     e[cnt].u=u; e[cnt].v=v;
18 }
19 int ru[N],cnnt;
20 int dir[4][2]= {0,0, 1,0, 0,1, 1,1};
21 int local[10][2]= {-1,-1, 0,0, 0,1, 0,2, 1,0, 1,1, 1,2, 2,0, 2,1, 2,2};
22 void topsort()
23 {
24     priority_queue<int>q;
25     for(int i=1;i<=9;i++)
26         if(ru[i]==0) q.push(i);
27     while(!q.empty())
28     { 
29         int x=q.top(); q.pop();
30         ++cnnt;
31     //    cout<<cnnt<<" ";
32         for(int i=first[x];i;i=e[i].nxt)
33         {
34             int v=e[i].v;
35             ru[v]--;
36             if(ru[v]==0) q.push(v);
37         }
38     }    
39     if(cnnt!=9) printf("THESE WINDOWS ARE BROKEN
");
40     else cout<<"THESE WINDOWS ARE CLEAN"<<endl;
41 }
42 int a[5][5];
43 bool vis[N][N];
44 int main()
45 {
46     char str[20];
47     while(scanf("%s",str),strcmp(str,"ENDOFINPUT"))
48     {
49         for(int i=0;i<4;i++)
50             for(int j=0;j<4;j++)
51                 scanf("%d",&a[i][j]);
52         scanf("%s",str);
53         memset(e,0,sizeof(e)); 
54         memset(vis,0,sizeof(vis));
55         memset(first,0,sizeof(first));
56         memset(ru,0,sizeof(ru));
57         cnt=cnnt=0;
58         for(int k=1;k<=9;k++)
59             for(int i=0;i<4;i++)//在自己射程区域内不是自己->被覆盖 
60             {
61                 int x=local[k][0]+dir[i][0];
62                 int y=local[k][1]+dir[i][1];
63                 int now=a[x][y];
64                 if(k!=now&&!vis[k][now])
65                 {
66                     vis[k][now]=1;
67                     ade(k,now);
68                     ru[now]++;
69                 }
70             }
71         topsort();
72     } 
73     return 0;
74 }