poj 2585 Window Pains

     格子覆盖问题，有两种方法。

     1.可以当做一道模拟题，每次找到一块完整的玻璃，将其取下，看最后能否将所有玻璃取下即可，因为数据量比较少，所以复杂度很低。

     2.可以看成一个AOV网络，寻找拓扑排序，看是否存在环，我就这样写的，但是昨晚把topo的dfs写错了o(╯□╰)o，今早查书才发现，dfs的拓扑是从后往前做topo，所以发现已存在在序列中的点是木有影响的。

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#define INF 1E9
using namespace std;
vector<int> map[16];
bool ok[10][10];
int vis[10];
void init()//确定每个点对应的窗口号
{
    int i,now=0;
    for(i=1;i<10&&now<15;i++)
    {
        map[now].push_back(i);
        map[now+1].push_back(i);
        map[now+4].push_back(i);
        map[now+5].push_back(i);
        now++;
        if(i%3==0)now++;
    }
    return;
}
bool dfs(int m)
{
    int i;
    vis[m]=-1;
    for(i=1;i<10;i++)
    {
        if(!ok[m][i])continue;
        if(vis[i]<0)return 0;//存在环
        if(!vis[i]&&!dfs(i))return 0;
    }
    vis[m]=1;
    return 1;
}
bool topo()
{
    for(int i=1;i<10;i++)
      if(!vis[i]&&!dfs(i))return 0;//增加人为排序
    return 1;
}
int main()
{
    init();
    string s;
    int i,t,j;
    while(cin>>s&&s!="ENDOFINPUT")
    {
        memset(vis,0,sizeof(vis));
        memset(ok,0,sizeof(ok));
        for(i=0;i<16;i++)
        {
           scanf("%d",&t);
           for(j=0;j<map[i].size();j++)
           {
               if(t==map[i][j])continue;
               ok[t][map[i][j]]=1;
           }
        }
        if(topo())cout<<"THESE WINDOWS ARE CLEAN"<<endl;
        else cout<<"THESE WINDOWS ARE BROKEN"<<endl;
        cin>>s;
    }
}