POJ 2585 Window Pains(拓扑排序判定)

POJ 2585 Window Pains(拓扑排序判定)

http://poj.org/problem?id=2585

题意:给你一个4*4的棋盘窗口,现在电脑上有9个应用,每个应用占用固定的2*2正方形网格位置.你通过不同的顺序操作9个应用可以使得4*4的窗口当前显示的内容(数字代表)不同,现在给你一个4*4棋盘窗口的内容,问你这个内容是否合法.

分析:其实本题就是一个判定拓扑排序是否存在的问题.把9个小窗口应用看成9个点,然后对于4*4的棋盘来说:

你看(1,2)这个方格当前放的是2数字,原本(1,2)方格我们能放的数有1和2两个数,现在放了2,说明从1应用->2应用有一条有向边.(也即是说应用1应先放,应用2后放,所以应用2能遮盖应用1).

现在来看(2,2)这个方格,这个方格是5,但是这个方格原先能放的应用有:1,2,4,5 四个应用.现在出现的应用是5,说明5是最后才放的应用.所以我们可知从应用1->5应用有一条有向边,从2->5,4->5都有一条有向边.

然后我们通过分析所有的4*4格子就能得到所有的有向边,得到G[10][10]数组和in[10]数组.

现在对于一个有向图,我们如何判断它能否拓扑排序呢?用刘汝佳的toposort()函数可以判断,但是这里不要求输出拓扑结果,我们只需要拆解该图即可,看看该图最终能否被完全拆解.(具体过程在数据结构C语言班,严蔚敏这本书上有详细介绍,看我的源代码应该也能懂)

拆解过程,就是从初态开始每次选取1个入度为0的点,删除从它出去的所有边,然后减小与这些边相关的点的入度.一直删除,直到找不到一个入度0的点位置.

如果最后图中还有点的度不为0,那么说明该有向图有环,无法拓扑排序.

这题还要注意,我们假设:如果(1,2)格子只能显示1或2,那么它就不可能显示3,4,5等数字. 输入中不会有这种数据.

注意:源代码中实现是应用0-8数字表示,且棋盘4*4也是从0开始计数的.程序中可能会重复添加有向边,一定要先判断当前G[i][j]是否==0.

AC代码:

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=10;
vector<int> value[maxn][maxn];
int dr[]={0,1,0,1};//原地,下,右,右下
int dc[]={0,0,1,1};
int G[maxn][maxn]; //图
int in[maxn];      //入度

bool topo()
{
    queue<int> Q;
    for(int i=0;i<9;i++)
        if(in[i]==0) Q.push(i);
    int sum=0;//记录我们删除的0入度点
    while(!Q.empty())
    {
        int u=Q.front(); Q.pop();
        for(int v=0;v<9;v++)if(G[u][v])
        {
            G[u][v]=0;
            if(--in[v]==0) Q.push(v);
        }
        sum++;
    }
    return sum==9;
}
int main()
{
    for(int i=0;i<9;i++)                //处理0-8每个应用所在的方格vector
    {
        int r=i/3, c=i%3;               //i应用左上角的格子所在的(r,c)
        for(int dir=0;dir<4;dir++)      //i应用所在的其他3个点
        {
            int nr=r+dr[dir], nc=c+dc[dir];
            value[nr][nc].push_back(i); //将i压入对应方格的vector中
        }
    }

    char str[100];
    while(scanf("%s",str)==1&&str[0]!='E')
    {
        memset(G,0,sizeof(G));
        memset(in,0,sizeof(in));
        for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
        {
            int v;
            scanf("%d",&v);
            v--;
            for(int k=0;k<value[i][j].size();k++)
            if((value[i][j])[k]!=v)//构造有向边
            {
                int x=(value[i][j])[k];
                if(G[x][v]==0)//一定要做这个判断,因为会重复添加有向边
                {
                    in[v]++;
                    G[x][v]=1;
                }
                //printf("当前格子为:(%d,%d),当前边为:%d v=%d, %d点的入度为%d\n",i,j,x,v,v,in[v]);
            }
        }
        if(topo()) printf("THESE WINDOWS ARE CLEAN\n");
        else printf("THESE WINDOWS ARE BROKEN\n");
        scanf("%s",str);
    }

    return 0;
}