[poj2585]Window Pains_拓扑排序

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
int cover[110][110][110];//记录当前格子可能出现的数字情况
int tail[110][110];//记录当前格子可能出现的数字个数
bool visit[110];//判断每一个点是否都进过队列
int v[110];//记录每个点的入度
bool map[110][110];//01矩阵，记录两点之间是否存在有向边
int a[110][110];//存储的是当前格子实际存在的数字
using namespace std;
void calc()//预处理每个格子所可能出现的数组(有些麻烦,仅供参考)
{
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=4;j++)
		{
			if(i==1||i==4)
			{
				if(j==1||j==4) tail[i][j]=1;
				else tail[i][j]=2;
			}
			else
			{
				if(j==1||j==4) tail[i][j]=2;
				else tail[i][j]=4;
			}
		}
	}
	cover[1][1][1]=1;
	cover[1][2][1]=1;cover[1][2][2]=2;
	cover[1][3][1]=2;cover[1][3][2]=3;
	cover[1][4][1]=3;
	cover[2][1][1]=1;cover[2][1][2]=4;
	cover[2][2][1]=1;cover[2][2][2]=2;cover[2][2][3]=4;cover[2][2][4]=5;
	cover[2][3][1]=2;cover[2][3][2]=3;cover[2][3][3]=5;cover[2][3][4]=6;
	cover[2][4][1]=3;cover[2][4][2]=6;
	cover[3][1][1]=4;cover[3][1][2]=7;
	cover[3][2][1]=4;cover[3][2][2]=5;cover[3][2][3]=7;cover[3][2][4]=8;
	cover[3][3][1]=5;cover[3][3][2]=6;cover[3][3][3]=8;cover[3][3][4]=9;
	cover[3][4][1]=6;cover[3][4][2]=9;
	cover[4][1][1]=7;
	cover[4][2][1]=7;cover[4][2][2]=8;
	cover[4][3][1]=8;cover[4][3][2]=9;
	cover[4][4][1]=9;
}
bool toposort()//裸toposort(拓扑排序)
{
	queue<int>q;
	while(q.size()) q.pop();
	for(int i=1;i<=9;i++)
	{
		if(!v[i])
		{
			q.push(i);visit[i]=true;
		}
	}
	while(q.size())
	{
		int x=q.front();q.pop();
		for(int i=1;i<=9;i++)
		{
			if(map[x][i])
			{
				v[i]--;
				if(v[i]==0)
				{
					q.push(i);visit[i]=true;
				}
			}
		}
	}
	for(int i=1;i<=9;i++)//判断数据是否合法
	{
		if(!visit[i]) return false;
	}
	return true;
}
void original()//初始化
{
	memset(visit,false,sizeof visit);
	memset(v,0,sizeof v);
	memset(a,0,sizeof a);
	memset(map,false,sizeof map);
}
int main()
{
	calc();
	while(1)
	{
		original();
		char s[100];
		scanf("%s",s+1);
		int k_k=strlen(s+1);
		if(k_k==10) break;
		bool flag=false;//临时记录当前数据是否满足第一个条件
		bool all=true;//记录所有数据是否都满足第一个条件
		for(int i=1;i<=4;i++)
		{
			for(int j=1;j<=4;j++)
			{
				scanf("%d",&a[i][j]);
				flag=false;
				for(int len=1;len<=tail[i][j];len++)
				{
					if(cover[i][j][len]==a[i][j])
					{
						flag=true;
					}
				}
				if(!flag) all=false;
			}
		}
		for(int i=1;i<=4;i++)//这里是建图的过程
		{
			for(int j=1;j<=4;j++)
			{
				for(int k=1;k<=tail[i][j];k++)
				{
					if(!map[a[i][j]][cover[i][j][k]]&&a[i][j]!=cover[i][j][k])
					{
						map[a[i][j]][cover[i][j][k]]=1;
						v[cover[i][j][k]]++;
					}
				}
			}
		}
		if(toposort()&&all) printf("THESE WINDOWS ARE CLEAN\n");//如果满足两个条件，数据才是合法的
		else printf("THESE WINDOWS ARE BROKEN\n");
		scanf("%s",s+1);
	}
	return 0;
}