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;
}