POJ2585 Window Pains，
Window Pains
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 1843
Accepted: 919
Description
Boudreaux likes to multitask, especially when it comes to using his computer. Never satisfied with just running one application at a time, he usually runs nine applications, each in its own window. Due to limited screen real estate, he overlaps these windows and brings whatever window he currently needs to work with to the foreground. If his screen were a 4 x 4 grid of squares, each of Boudreaux's windows would be represented by the following 2 x 2 windows:
1
1
.
.
1
1
.
.
.
.
.
.
.
.
.
.
.
2
2
.
.
2
2
.
.
.
.
.
.
.
.
.
.
.
3
3
.
.
3
3
.
.
.
.
.
.
.
.
.
.
.
.
4
4
.
.
4
4
.
.
.
.
.
.
.
.
.
.
.
5
5
.
.
5
5
.
.
.
.
.
.
.
.
.
.
.
6
6
.
.
6
6
.
.
.
.
.
.
.
.
.
.
.
.
7
7
.
.
7
7
.
.
.
.
.
.
.
.
.
.
.
8
8
.
.
8
8
.
.
.
.
.
.
.
.
.
.
.
9
9
.
.
9
9
When Boudreaux brings a window to the foreground, all of its squares come to the top, overlapping any squares it shares with other windows. For example, if window
1and then window
2 were brought to the foreground, the resulting representation would be:
1
2
2
?
1
2
2
?
?
?
?
?
?
?
?
?
If window
4 were then brought to the foreground:
1
2
2
?
4
4
2
?
4
4
?
?
?
?
?
?
. . . and so on . . .
Unfortunately, Boudreaux's computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly. And this is where you come in . . .
Input
Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.
A single data set has 3 components:
After the last data set, there will be a single line:
ENDOFINPUT
Note that each piece of visible window will appear only in screen areas where the window could appear when brought to the front. For instance, a 1 can only appear in the top left quadrant.
Output
For each data set, there will be exactly one line of output. If there exists a sequence of bringing windows to the foreground that would result in the graphical representation of the windows on Boudreaux's screen, the output will be a single line with the statement:
THESE WINDOWS ARE CLEAN
Otherwise, the output will be a single line with the statement:
THESE WINDOWS ARE BROKEN
Sample Input
START
1 2 3 3
4 5 6 6
7 8 9 9
7 8 9 9
END
START
1 1 3 3
4 1 3 3
7 7 9 9
7 7 9 9
END
ENDOFINPUT
Sample Output
THESE WINDOWS ARE CLEAN
THESE WINDOWS ARE BROKEN
題目鏈接：http://poj.org/problem?id=2585
題意：
有一個擁有4×4網格的顯示屏，有9個2×2的程序窗口，把一個窗口調到最前時，它的所有方格中的數字都位於最前，覆蓋共用的方格。按照不同的順序將窗口調到最前，但是計算機很不穩定，經常崩潰。輸入的窗口的狀態，判斷是否能出現這樣的窗口狀態。可以的話說明計算機沒有崩潰，輸出“THESE WINDOWS ARE CLEAN”，否則輸出“THESE WINDOWS ARE BROKEN”。
每組數據已“START”開始，已“END”結束。中間是方格數字顯現的狀態。如果輸入“ENDOFINPUT”就結束輸入。
計算機每個方格中擁有的數字：
1
1,2，
2,3，
3
1,4
1,2,4,5
2,3,5,6
3,6
4
4,5
5,6,8,9
6,9
7
7,8
8,9
9
那麼相應方格中顯示出來的數字就覆蓋了相應方格中那些其他的數字。覆蓋之間建立一條邊，最終形成的圖是否正常。
這就是一個拓撲排序問題，圖中不能有環，有環說明不合理，也就是計算機崩潰。無環說明圖合理。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 int L[10][10];
6 int indegree[10];
7 int TopSort();
8 int main()
9 {
10 int i,j,t;
11 string cover[5][5];
12 for(i=0; i<3; i++)
13 {
14 for(j=0; j<3; j++)
15 {
16 cover[i][j]+=j+1+i*3+'0';
17 cover[i][j+1]+=j+1+i*3+'0';
18 cover[i+1][j]+=j+1+i*3+'0';
19 cover[i+1][j+1]+=j+1+i*3+'0';
20 }
21 }
22 /**
23 for(i=0; i<4; i++)
24 {
25 for(j=0; j<4; j++)
26 {
27 string::iterator y;
28 for (y=cover[i][j].begin(); y!=cover[i][j].end(); ++y)
29 {
30 cout<<*y;
31 }
32 cout<<" ";
33 }
34 cout<<endl;
35 }
36 */
37 string s;
38 while(cin>>s)
39 {
40 getchar();
41 if(s=="ENDOFINPUT") break;
42 memset(indegree,0,sizeof(indegree));
43 memset(L,0,sizeof(L));
44 for(i=0; i<4; i++)
45 {
46 for(j=0; j<4; j++)
47 {
48 char x;
49 scanf("%c",&x);
50 string::iterator y;
51 for (y=cover[i][j].begin(); y!=cover[i][j].end(); ++y)
52 {
53 if((*y)!=x&&L[x-'0'][(*y)-'0']==0)
54 {
55 L[x-'0'][(*y)-'0']=1;
56 indegree[(*y)-'0']++;
57 }
58 }
59 getchar();
60 }
61 }
62 cin>>s;
63 getchar();
64 /**
65 for(i=1; i<10; i++)
66 {
67 cout<<i<<":";
68 for(j=0; j<10; j++)
69 {
70 if(L[i][j]==1)
71 cout<<j<<" ";
72 }
73 cout<<endl;
74 }
75 cout<<"indegree:";
76 for(i=1; i<10; i++) cout<<indegree[i]<<" ";
77 cout<<endl;
78 */
79 int flag=TopSort();
80 if(flag) cout<<"THESE WINDOWS ARE CLEAN"<<endl;
81 else cout<<"THESE WINDOWS ARE BROKEN"<<endl;
82 }
83 return 0;
84 }
85 int TopSort()
86 {
87 int i,j;
88 int n=9;
89 int sign=0;
90 while(n--)
91 {
92 sign=0;
93 for(i=1; i<10; i++)
94 {
95 if(indegree[i]==0) sign=i;
96 }
97 if(sign>0)
98 {
99 for(j=0; j<10; j++)
100 {
101 if(L[sign][j])
102 indegree[j]--;
103 }
104 indegree[sign]=-1;
105 }
106 else if(sign==0) return 0;
107 }
108 return 1;
109 }
View Code
