[POJ 2585] Window Pains (拓扑排序)
时间:2014-03-16 17:20:24
收藏:0
阅读:567
Window Pains
题目链接:http://poj.org/problem?id=2585
题目大意:
有4*4的网格,其中有九个任务,在网格上的位置如下。 现在依次打开几个任务,在同一个网格上,前一个任务会覆盖掉后一个任务。给你一个网格,问你能否通过调整先后顺序,使得构成该网格。
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
这副图就表示先打开1,后打开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}};
,{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 <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <queue> #include <vector> #include <set> #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<int> 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<int> 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<int>::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; }
[POJ 2585] Window Pains (拓扑排序),布布扣,bubuko.com
原文:http://blog.csdn.net/sio__five/article/details/21329029
评论(0)