Window Pains
题目链接：http://poj.org/problem?id=2585
题目大意： 有4*4的网格，其中有九个任务，在网格上的位置如下。 现在依次打开几个任务，在同一个网格上，前一个任务会覆盖掉后一个任务。给你一个网格，问你能否通过调整先后顺序，使得构成该网格。
| 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 |
|
这副图就表示先打开1，后打开2.
| 1 |
2 |
2 |
? |
| 1 |
2 |
2 |
? |
| ? |
? |
? |
? |
| ? |
? |
? |
? |
|
解题思路： 由于不同任务有先后顺序，我们其实是要得到就是符合这些顺序的一组序列。所以是拓扑排序，关键是如何建立这些关系。 可以看到不同的网格上，可以出现的数字是不一样的。 下面是4*4个网格中分别可以出现的数字： {{1}, {1, 2}, {2, 3}, {3}
,{1, 4}, {1, 2, 4, 5}, {2, 3, 5, 6}, {3, 6}
,{4, 7}, {4, 5, 7, 8}, {5, 6, 8, 9}, {6, 9}
,{7}, {7, 8}, {8, 9}, {9}};
在同一个网格上，网格上的数字一定是比该网格上的可以出现的其他数字后调用，所以可以在每个网格上可以建立先后关系。然后就是判断是否能拓扑排序。具体实现见代码。
代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a, b) memset(a, b, sizeof(a)) using namespace std; int has[10]; int ge[20][6] = {{1}, {1, 2}, {2, 3}, {3} ,{1, 4}, {1, 2, 4, 5}, {2, 3, 5, 6}, {3, 6} ,{4, 7}, {4, 5, 7, 8}, {5, 6, 8, 9}, {6, 9} ,{7}, {7, 8}, {8, 9}, {9}}; int cnt[20] = {1, 2, 2, 1, 2, 4, 4, 2, 2, 4, 4, 2, 1, 2, 2, 1}; set
V[15]; int g[15][15], du[15]; int shu[20], in[15]; bool toposort() { mem(du, 0); for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) if (g[i][j]) du[j]++; queue
q; int tot = 0; for (int i = 1; i <= 9; i++) if (!du[i]) q.push(i); while(!q.empty()) { int u = q.front(); q.pop(); tot++; set
::iterator it; for (it = V[u].begin(); it != V[u].end(); it++) { int v = *it; du[v]--; if (!du[v]) q.push(v); } } if (tot == 9) return 1; return 0; } int main () { char str[20]; while(gets(str)) { if (str[0] == 'E') break; mem(has, 0); mem(g, 0); for (int i = 1; i <= 9; i++) V[i].clear(); for (int i = 0; i < 16; i++) { scanf("%d", shu + i); has[shu[i]] = 1; } int ok = 0; for (int i = 0; i < 16; i++) { int u = shu[i], l = cnt[i]; for (int j = 0; j < l; j++) { int v = ge[i][j]; if (v != u && has[v]) { V[v].insert(u); g[v][u] = 1; } if (v == u) ok++; } } if (ok == 16 && toposort()) puts("THESE WINDOWS ARE CLEAN"); else puts("THESE WINDOWS ARE BROKEN"); getchar(); gets(str); } return 0; }
|