题目：http://poj.org/problem?id=2585
题意就是有一个4*4方格，还有一些2*2的窗口，特定的窗口在屏幕中特定的位置出现，并且后出现的可以覆盖先出现的，然后给你一个屏幕，判断它是不是处于正常状态，总体思路就是先建图，然后拓扑排序一下就ok了，这里比较麻烦的就是建图上，由于每个窗口只会在它可能出现的位置出现，所以只需要首先把每一个位置可能出现的全部覆盖的情况找出来即可，这里用的是一个数组cover[i][j][k]表示在i，j这个位置上会被cover[i][j][k]这个窗口覆盖，cover[i][j][0]，是用来记录在该处总共会被覆盖的敞口数，然后还有一点要注意的就是如果同时有多个位置发生窗口a被窗口b覆盖，建图时只能画一条有向边的
代码：
#include<cstdio> #include<cstring> char str[20]; int id[10]; bool used[10]; int Edge[10][10]; int cover[10][10][5]; int cnt[10][10];//用来暂时记录(i, j)处已经被覆盖的窗口数 int total; void init() {//对cover的初始化 for(int i = 0; i < 4; ++ i) { for(int j = 0; j < 4; ++ j) { cnt[i][j] = 1; } } for(int n = 1; n <= 9; ++ n) { int x= (n-1)/3; int y = (n-1)%3; cover[x][y][cnt[x][y]++] = n; cover[x+1][y][cnt[x+1][y]++] = n; cover[x][y+1][cnt[x][y+1]++] = n; cover[x+1][y+1][cnt[x+1][y+1]++] = n; } for(int i = 0; i < 4; ++ i) { for(int j = 0; j < 4; ++ j) { cover[i][j][0] = cnt[i][j] - 1; } } } bool toposort() { int count = 0; while(total) { int m = -1; for(int i = 1; i <= 9; ++ i) { if(!used[i] || id[i] > 0) { continue; } m = i; break; } if(m == -1 && total != 0) { return false; } else {//找到入度为零的点后，删除该点已经该点发出的所有边 used[m] = false; total--; for(int j = 1; j <= 9; ++ j) { if(Edge[m][j] == 1) { id[j]--; Edge[m][j] = 0; } } } } return true; } int main() { freopen("poj2585.txt", "r", stdin); init(); while(scanf("%s", str) && strcmp(str, "ENDOFINPUT") != 0) { memset(id, 0, sizeof(id)); memset(used, false, sizeof(used)); memset(Edge, 0, sizeof(Edge)); int temp; total = 0; for(int i = 0; i < 4; ++ i) { for(int j = 0; j < 4; ++ j) { scanf("%d", &temp); if(!used[temp]) { total ++; used[temp] = true; } for(int k = 1; k <= cover[i][j][0]; ++ k) { if(Edge[temp][cover[i][j][k]] == 0 && cover[i][j][k] != temp) { Edge[temp][cover[i][j][k]] = 1; id[cover[i][j][k]]++; } } } } if(toposort()) { printf("THESE WINDOWS ARE CLEAN\n"); } else { printf("THESE WINDOWS ARE BROKEN\n"); } scanf("%s", str); } return 0; } |