2078.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2078 on 2005-09-22 at 20:34:05 */ 
#include <stdio.h>
#include <string.h>
#include <memory.h>

int haveCircle(void);

int m[10][10];

int main()
{
    int window[4][4];
    char order[12];
    int i, j, shdap;
    
    while(scanf("%s", order) == 1) {
        if(!strcmp(order, "ENDOFINPUT")) {
            return 0;
        } else {
            for(i = 0; i < 4; i++) {
                for(j = 0; j < 4; j++) {
                    scanf("%d", &window[i][j]);
                }    
            }
            scanf("%s", order);
            memset(m, 0, sizeof(m));
            for(i = 0; i < 4; i++) {
                for(j = 0; j < 4; j++) {
                    if(i != 3) {
                        if(j != 0) {
                            shdap = i * 3 + j;
                            if(shdap != window[i][j]) {
                                m[window[i][j]][shdap] = 1;
                            }
                        }
                        if(j != 3) {
                            shdap = i * 3 + j + 1;
                            if(shdap != window[i][j]) {
                                m[window[i][j]][shdap] = 1;
                            }
                        }    
                    }
                    if(i != 0) {
                        if(j != 0) {
                            shdap = (i-1) * 3 + j;
                            if(shdap != window[i][j]) {
                                m[window[i][j]][shdap] = 1;
                            }
                        }
                        if(j != 3) {
                            shdap = (i-1) * 3 + j + 1;
                            if(shdap != window[i][j]) {
                                m[window[i][j]][shdap] = 1;
                            }
                        }
                    }    
                }
            }    
            if(haveCircle()) {
                printf("THESE WINDOWS ARE BROKEN\n");
            } else {
                printf("THESE WINDOWS ARE CLEAN\n");
            }    
        }
    }
    
    return 0;
}

int haveCircle(void)
{
    int i, j, top = 0, k;
    int inStack[10] = {0}, stack[10];
    int inDeg[10] = {0};
    
    for(i = 1; i < 10; i++) {
        for(j = 1; j < 10; j++) {
            if(m[j][i] == 1) {
                inDeg[i]++;
            }    
        }    
    }
    while(1) {
        for(i = 1; i < 10; i++) {
            if(inDeg[i] == 0 && !inStack[i]) {
                stack[top++] = i;
                inStack[i] = 1;
            }
        }
        if(top == 0) {
            for(i = 1; i < 10; i++) {
                if(inStack[i] == 0) {
                    return 1;
                }    
            }
            return 0;
        } else {
            k = stack[--top];
            for(i = 1; i < 10; i++) {
                if(m[k][i] == 1) {
                    inDeg[i]--;
                }    
            }    
        }    
    }    
}