Window Pains（poj 2585）

题意：

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

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

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

分析：拓扑排序，把完全出现的数字拿出来，位置置空，然后再找下一个完全出现的数，直到找完为止，若中途找不到，则不合法。

代码：

#include<cstdio>

#include<iostream>

 #include<cstring>

using namespace std;

int map[],pos[][],vis[];

void init()

{

    int i=,j=;

    while(i<=)

    {

        pos[i][]=j;pos[i][]=j+;pos[i][]=j+;pos[i][]=j+;

        if(i%==)j+=;

        else j+=;

        i++;

    }

}

bool ok(int x)

{

    for(int i=;i<=;i++)

      if(map[pos[x][i]]!=x&&map[pos[x][i]]!=)

        return false;

    return true;

}

void work()

{

    int tot=;

    while()

    {

        int k=;

        for(int i=;i<=;i++)

          if(!vis[i]&&ok(i))

          {

              tot++;

              vis[i]=;

              k=i;

              break;

          }

        if(!k)break;

        for(int i=;i<=;i++)

          map[pos[k][i]]=;

    }

    if(tot<)printf("THESE WINDOWS ARE BROKEN\n");

    else printf("THESE WINDOWS ARE CLEAN\n");}int main(){

    init();

    while()

    {

        memset(vis,,sizeof(vis));

        string s;cin>>s;

        if(s[]=='O')break;

        for(int i=;i<=;i++)

          scanf("%d",&map[i]);

        work();

        cin>>s;

    }

    return ;

}