题目链接：

题意：
一快屏幕分很多区域，区域之间可以相互覆盖，要覆盖就把属于自己的地方全部覆盖。给出这块屏幕最终的位置，看这块屏幕是对的还是错的。。
思路：
拓扑排序，这个简化点说，就是说跟楚河汉界一样，，分的清清楚楚，要么这块地方是我的，要么这块地方是你的，不纯在一人一办的情况，所以如果排序的时候出现了环，那么就说这快屏幕是坏的。。。还有一点细节要注意的是第i个数字到底属于第几行第几列，所以这个要发现规律，然后一一枚举就可以了。。

题目：

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

THESE WINDOWS ARE CLEAN
THESE WINDOWS ARE BROKEN

代码为：

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=5+10;
int map[maxn][maxn],in[maxn];

queue<int>Q;
vector<int>vec[maxn];
int dx[]={0,0,1,1};
int dy[]={0,1,0,1};

int topo()
{
    int sum=9;
    while(!Q.empty())  Q.pop();
    for(int i=1;i<=9;i++)
    {
        if(in[i]==0)
            Q.push(i);
    }
    while(!Q.empty())
    {
        int temp=Q.front();
        Q.pop();
        sum--;
        for(int i=0;i<vec[temp].size();i++)
        {
            if(--in[vec[temp][i]]==0)
                Q.push(vec[temp][i]);
        }
    }
    if(sum>0)  return 0;
    else    return 1;
}

void init()
{
    char str[10];
    for(int i=1;i<=9;i++)
    {
        vec[i].clear();
        in[i]=0;
    }
    for(int i=1;i<=9;i++)
    {
        int x=(i-1)/3+1;
        int y=i%3==0?3:i%3;
        for(int j=0;j<=3;j++)
        {
             int tx=x+dx[j];
             int ty=y+dy[j];
             if(map[tx][ty]!=i)
             {
                 vec[i].push_back(map[tx][ty]);
                 in[map[tx][ty]]++;
             }
        }
    }
    scanf("%s",str);
}

void solve()
{
    int  ans=topo();
    if(ans)
        cout<<"THESE WINDOWS ARE CLEAN"<<endl;
    else
        cout<<"THESE WINDOWS ARE BROKEN"<<endl;
}


int main()
{
    char str[10];
    while(~scanf("%s",str))
    {
        if(strcmp(str,"ENDOFINPUT")==0)  return 0;
        for(int i=1;i<=4;i++)
            for(int j=1;j<=4;j++)
              scanf("%d",&map[i][j]);
        init();
        solve();
    }
    return 0;
}

pojWindow Pains（拓扑排序）,布布扣,bubuko.com

pojWindow Pains（拓扑排序）