学步园

题目链接:    http://poj.org/problem?id=2585

题目大意:    在给定的4x4的矩阵中会出现9个数字

                   每个数字的出现为2x2矩阵

                   出现的位置是不同的

                   先出现的数字会被后出现的数字覆盖

                   依次出现这九个数字(顺序不定)，给出最后的图

                   求他们是否满足情况?

解题思路:    在第i个数字出现的2x2矩阵中扫描出现的数字，这四个数字是否等于i

                   如果不等于i,说明这个数字肯定在i之后出现

                   先出现的数字为边的起点，后面出现的数字为边的终点构成有向边

                   以此类推最终构成有向图

                   数字的出现有先后之分，所以边的遍历只能从起点走向终点

                   起点必须比终点先走，因为这个数字先出现

                   如果走的顶点的顺序有冲突，再次回到走过的点，就不满足题意

                   也就是在这个图里能不能找到有向环?

                   AOV网络中如果出现了有向回路，则意味着某项活动以自己作为先决条件，这是不对的！

                   可以用拓扑排序来找到有向环

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 4
#define MAX_2 10
int edge[MAX_2][MAX_2],pains[MAX][MAX],dist[MAX_2];

int topsort()   //拓扑排序寻找有向环
{
    int i,u0,e,s,t,list[100]; //队列或栈都能实现拓扑排序
    e=s=t=0;
    for(i=1;i<=9;i++)
    {
        if(dist[i]==0)        //初始化把入度为0的顶点加入队列
        {
            list[e++]=i;
        }
    }
    while(e!=s)
    {
        u0=list[s++];
        t++;
        for(i=1;i<=9;i++)
        {
            if(edge[u0][i]==1)
            {
                dist[i]--;
                if(dist[i]==0)   //边的入度为0,入队
                {
                    list[e++]=i;
                }
            }
        }
    }
    if(t==9)       //出队列的顶点数等于9,则条件满足
        return 1;
    else           //否则错误
        return 0;
}

int main()
{
    char ch[15];
    int n,i,j,k,a,b,c;
    while(scanf("%s",ch)!=EOF)
    {
        if(strcmp(ch,"ENDOFINPUT")==0)
            break;
        memset(dist,0,sizeof(dist));
        memset(edge,0,sizeof(edge));
        for(i=0;i<MAX;i++)
        {
            for(j=0;j<MAX;j++)
            {
                scanf("%d",&pains[i][j]);
            }
        }
        for(i=0,k=0;i<3;i++)
        {
            for(j=0;j<3;j++) 
            {
                k++;
                a=b=c=-1;     //***a,b,c为了防止这些数字有重复,重复增加顶点的入度,会WA
                if(pains[i][j]!=k)
                {
                    edge[k][pains[i][j]]=1;
                    dist[pains[i][j]]++;
                    a=pains[i][j];
                }
                if(pains[i][j+1]!=k)
                {
                    edge[k][pains[i][j+1]]=1;
                    if(pains[i][j+1]!=a)   //不重复则增加入度
                    {
                        dist[pains[i][j+1]]++;
                        b=pains[i][j+1];
                    }
                }
                if(pains[i+1][j]!=k)
                {
                    edge[k][pains[i+1][j]]=1;
                    if(pains[i+1][j]!=a&&pains[i+1][j]!=b)  //不重复则增加入度
                    {
                        dist[pains[i+1][j]]++;
                        c=pains[i+1][j];
                    }
                }
                if(pains[i+1][j+1]!=k)
                {
                    if(pains[i+1][j+1]!=a&&pains[i+1][j+1]!=b&&pains[i+1][j+1]!=c)
                    {                           //不重复则增加入度
                        edge[k][pains[i+1][j+1]]=1;
                        dist[pains[i+1][j+1]]++;
                    }
                }
            }
        }
        n=topsort();
        if(n==0)
            printf("THESE WINDOWS ARE BROKEN\n");
        else
            printf("THESE WINDOWS ARE CLEAN\n");
        scanf("%s",ch);
    }
    return 0;
}

注：原创文章，转载请注明出处