[ZOJ 2193] Window Pains
Opened this issue · 0 comments
ZOJ2193 - Window Pains
题目
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 . . . 2 2 . . . 3 3
1 1 . . . 2 2 . . . 3 3
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
4 4 . . . 5 5 . . 6 6 .
4 4 . . . 5 5 . . 6 6 .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
7 7 . . . 8 8 . . . 9 9
7 7 . . . 8 8 . . . 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 1 and 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:
- Start line - A single line:
START - Screen Shot - Four lines that represent the current graphical representation of the windows on Boudreaux's screen. Each position in this 4 x 4 matrix will represent the current piece of window showing in each square. To make input easier, the list of numbers on each line will be delimited by a single space.
- End line - A single line:
END
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
分析
如果知道拓扑排序的话应该很容易知道这道题要用拓扑排序来解决。
不看题目看例子也可以看懂题目的意思了~
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。
- 每个顶点出现且只出现一次；
- 若A在序列中排在B的前面，则在图中不存在从B到A的路径。
也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。
进行拓扑排序，有以下步骤：
- 输入AOV网络。令n为顶点个数。
- 在AOV网络中选择一个入度为0的结点，并输出之。
- 从图中删去该顶点，同时删去所有它发出的有向边。
- 重复以上2，3步，直到下面的情况之一出现：
- 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成。
- 图中还有未输出的顶点，但已没有入度为0的结点（说明网络中必定存在有向环）。
接下来来看下这道题。
进行拓扑排序第一步是建立邻接矩阵和他们的度数。我们要知道这个邻接矩阵表示的是什么和什么之间的关系。对于这道题，邻接矩阵是用来表示窗口i可以覆盖哪些窗口。比如对于此题的第一个例子，我们建立邻接矩阵如下图：
所以建立出来的邻接矩阵如下。G[I][J]为1时表示窗口I可以覆盖窗口J。
G[10][10]
G[0] 0 0 0 0 0 0 0 0 0 0
G[1] 0 0 0 0 0 0 0 0 0 0
G[2] 0 1 0 0 0 0 0 0 0 0
G[3] 0 0 1 0 0 0 0 0 0 0
G[4] 0 1 0 0 0 0 0 0 0 0
G[5] 0 1 1 0 1 0 0 0 0 0
G[6] 0 0 1 1 0 1 0 0 0 0
G[7] 0 0 0 0 1 0 0 0 0 0
G[8] 0 0 0 0 1 1 0 1 0 0
G[9] 0 0 0 0 0 1 1 0 1 0
同时记录下indegree[9]表示窗口i的入度。
接着使用拓扑排序算法即可。
程序
// 拓扑排序
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int a[4][4];
bool exist[10];
string cover[4][4];
int G[10][10];
int indegree[10];
int type; // 输入的数的类型
void buildG() { // 构造有向图
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int p = 0; p < cover[i][j].length(); p++) {
int from = a[i][j],
to = cover[i][j][p] - '0';
// [i][j]到所有[i][j]可能覆盖点，建立邻接矩阵
if (G[from][to] == 0 && from != to && exist[from] && exist[to]) {
G[from][to] = 1;
indegree[from] ++;
}
}
}
}
}
bool check() { // 判断是否有环，无环返回true，有环返回false
for (int i = 0; i < type; i++) {
int count = 0; // 计算当前入度等于0的窗口数
int number = 0; // 记录当前窗口数
for (int j = 1; j <= 9; j++) {
if (exist[j] && indegree[j] == 0) {
count++;
}
if (exist[j]) {
number++;
}
}
// 如果已经没有入度为0的窗口而当前窗口还不为0，则返回false
if (count == 0 && number > 0) {
return false;
}
int k=0;
// 找到入度为0的点
for (int j = 1; j <= 9; j++) {
if (exist[j] && indegree[j] == 0) {
k = j;
break;
}
}
exist[k] = false;
for (int j = 1; j <= 9; j++)
if (exist[j] && G[j][k])
// 删除相应顶点入边(入度减1)
indegree[j]--;
}
}
int main() {
string str;
for (int i = 1; i <= 9; i++) { // cover表示(i,j)处可能的覆盖
int t = (i-1) / 3;
int k = (i-1) % 3;
cover[t][k] += char(i + '0');
cover[t][k + 1] += char(i + '0');
cover[t + 1][k] += char(i + '0');
cover[t + 1][k + 1] += char(i + '0');
}
while (cin >> str && str != "ENDOFINPUT") {
memset(exist, 0, sizeof(exist));
memset(indegree, 0, sizeof(indegree));
memset(G, 0, sizeof(G));
type = 0;
for (int i = 0; i < 4; i++) { // 输入数据
for (int j = 0; j < 4; j++) {
cin >> a[i][j];
if (!exist[a[i][j]]) type++;
exist[a[i][j]] = true;
}
}
buildG();
if (check()) {
cout << "THESE WINDOWS ARE CLEAN" << endl;
}
else {
cout << "THESE WINDOWS ARE BROKEN" << endl;
}
string s;
cin >> s;
}
return 0;
}