Window Pains（poj 2585）

题意：

一个屏幕要同时打开9个窗口，每个窗口是2*2的矩阵，整个屏幕大小是9*9，每个窗口位置固定。

但是是否被激活（即完整显示出来）不确定。

给定屏幕状态，问是否可以实现显示。

分析：拓扑排序，把完全出现的数字拿出来，位置置空，然后再找下一个完全出现的数，直到找完为止，若中途找不到，则不合法。
代码：
#include<cstdio> 
#include<iostream>
 #include<cstring> 
using namespace std;
int map[20],pos[10][5],vis[10];
void init()
{
    int i=1,j=1;
    while(i<=9)
    {
        pos[i][1]=j;pos[i][2]=j+1;pos[i][3]=j+4;pos[i][4]=j+5;
        if(i%3==0)j+=2;
        else j+=1;
        i++;
    }
}
bool ok(int x)
{
    for(int i=1;i<=4;i++)
      if(map[pos[x][i]]!=x&&map[pos[x][i]]!=0)
        return false;
    return true;
}
void work()
{
    int tot=0;
    while(1)
    {
        int k=0;
        for(int i=1;i<=9;i++)
          if(!vis[i]&&ok(i))
          {
              tot++;
              vis[i]=1;
              k=i;
              break;
          }
        if(!k)break;
        for(int i=1;i<=4;i++)
          map[pos[k][i]]=0;
    }
    if(tot<9)printf("THESE WINDOWS ARE BROKEN
");
    else printf("THESE WINDOWS ARE CLEAN
");}int main(){
    init();
    while(1)
    {
        memset(vis,0,sizeof(vis));
        string s;cin>>s;
        if(s[3]=='O')break;
        for(int i=1;i<=16;i++)
          scanf("%d",&map[i]);
        work();
        cin>>s;
    }
    return 0;
}