【POJ】[2585]Window Pains

问题描述

Window Pains

[poj-2585] [3219815653601074] @vjudge

问题分析

理解之后算是道比较水的题。

因为对于每一个网格，如果网格内的数字不是相同的，则网格内的数字必然出现的比应该出现的那个晚，这样把map遍历一遍，便可得到关于1~9的有向图，剩下就是看其能否topo排序，如果无环则这个图形就能出现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<stdio.h>
#include<string.h>
char s[20];
int map[5][5];
int edge[12][12];
int cnt[12];
bool topo() {
	int num=0;
	for(int i=1; i<=9; i++) {
		for(int j=1; j<=9; j++) {
			if(cnt[j]==0) {
				cnt[j]--;
				num++;
				for(int k=1; k<=9; k++) {
					if(edge[j][k]==1) {
						cnt[k]--;
					}
				}
				break;
			}
		}
	}
	return num==9;
}
int main() {
	while(scanf("%s",s),strcmp(s,"ENDOFINPUT")!=0) {
		memset(edge,0,sizeof(edge));
		memset(cnt,0,sizeof(cnt));
		for(int i=1; i<=4; i++)
			for(int j=1; j<=4; j++)
				scanf("%d",&map[i][j]);
 
		scanf("%s",s);
		for(int i=1; i<=3; i++) {
			for(int j=1; j<=3; j++)
				for(int in=0; in<2; in++) {
					for(int im=0; im<2; im++) {
 
						if(map[i+in][j+im]==j+(i-1)*3)
							continue;
						else if(edge[map[i+in][j+im]][j+(i-1)*3]==0) {
							edge[map[i+in][j+im]][j+(i-1)*3]=1;
 
							cnt[j+(i-1)*3]++;
						}
					}
				}
		}
		printf("%s\n",topo()?"THESE WINDOWS ARE CLEAN":"THESE WINDOWS ARE BROKEN");
	}
	return 0;
}