麻烦的窗口

【题目描述】

小明从来没有一次运行1个应用程序，他通常运行9个应用程序，每个应用程序都在自己的窗口中运行。由于有限的屏幕空间，他会重叠这些窗口。如果他的屏幕是4×4正方形网格，每个窗口将由以下2x2的窗口表示：

重叠的任何一个窗口将会被上面的窗口所覆盖。例如，窗口1和窗口2先后被打开，最终表示为：

如果再打开窗口4：

【输入描述】

设计一个程序，判断此窗口是否合法。

包含n(n <= 100)组测试数据，每组测试数据由以下三部分组成：

(1)一行：START；

(2)一个4×4的数字网格；

(3)一行：END；

输入结束有一行：ENDOFINPUT。

【输出描述】

对于每组测试数据，判断其是否合法。如果合法，输出：THESE WINDOWS ARE CLEAN；如果不合法，输出：THESE WINDOWS ARE BROKEN。

【样例输入】

START

1 2 3 3

4 5 6 6

7 8 9 9

END

START

1 1 3 3

4 1 3 3

7 7 9 9

END

ENDOFINPUT

【样例输出】

THESE WINDOWS ARE CLEAN

THESE WINDOWS ARE BROKEN

源代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
bool f[15][15];
int Map[5][5],i[15];
int x[4]={0,1,0,1},y[4]={0,0,1,1};
int X_has[10]={0,1,2,3,1,2,3,1,2,3},Y_has[10]={0,1,1,1,2,2,2,3,3,3};
void Add(int u,int v)
{
    if (!f[u][v])
    {
        f[u][v]=true;
        i[v]++;
    }
}
bool Topsort()
{
    int sum=0;
    queue <int> h;
    for (int a=1;a<=9;a++)
      if (!i[a])
        h.push(a);
    while (!h.empty())
    {
        int Now=h.front();
        h.pop();
        sum++;
        for (int a=1;a<=9;a++)
        {
            if (f[Now][a])
            {
                i[a]--;
                if (!i[a])
                  h.push(a);
            }
        }
    }
    if (sum==9)
      return true;
    return false;
}
void Solve()
{
    memset(f,0,sizeof(f)); //初始化。
    memset(i,0,sizeof(i));
    for (int a=1;a<=9;a++)
    {
        int X=X_has[a];
        int Y=Y_has[a];
        for (int b=0;b<4;b++)
        {
            int t1=X+x[b];
            int t2=Y+y[b];
            if (Map[t2][t1]!=a)
              Add(Map[t2][t1],a);
        }
    }
    if (Topsort())
      printf("THESE WINDOWS ARE CLEAN
");
    else
      printf("THESE WINDOWS ARE BROKEN
");
}
int main()
{
    char t[10];
    while (scanf("%s",t)&&t[0]=='S')
    {
        for (int a=1;a<=4;a++)
          for (int b=1;b<=4;b++)
            scanf("%d",&Map[a][b]);
        Solve();
        scanf("%s",t);
    }  
    return 0;
}