[poj2585]Window Pains_拓扑排序
Window Pains poj-2585
题目大意：给出一个4*4的方格表，由9种数字组成。其中，每一种数字只会出现在特定的位置，后出现的数字会覆盖之前在当前方格表内出现的。询问当前给出的方格表是否合法。
注释：输入格式需要注意。
想法：toposort裸题，我们先预处理出每一个格子可能出现的数字，如果当前数字根本不可能出现在当前格子里，那么就一定是不合法的。如果满足了第一个条件，那么如果当前数字覆盖了本应该在当前格子里出现的数字，我就以当前数字想本应该出现数字之间连一条有向边。然后，不合法的条件就是出现环，因为不可能出现A覆盖B，B又覆盖A的情况。我们在这里采用toposort判环，如果存在一个点没有进队，那么这组数据就是不合法的。
最后，附上 丑陋的代码... ...
#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;
}
小结：toposort的一个应用，判环。相较于bellmanford的优点就是toposort是O(n)，相较于spfa的优点就是没有可以特意hack掉的数据。
