Frame Stacking

題目鏈接：http://poj.org/problem?id=1128
題目大意：

........ ........ ........ ........ .CCC....

EEEEEE.. ........ ........ ..BBBB.. .C.C....

E....E.. DDDDDD.. ........ ..B..B.. .C.C....

E....E.. D....D.. ........ ..B..B.. .CCC....

E....E.. D....D.. ....AAAA ..B..B.. ........

E....E.. D....D.. ....A..A ..BBBB.. ........

E....E.. DDDDDD.. ....A..A ........ ........

E....E.. ........ ....AAAA ........ ........

EEEEEE.. ........ ........ ........ ........

    1        2        3        4        5   

在9 * 8 的網格上，有上述5張圖片。現在將他們擺放到同一個網格上。 如下圖所示：

.CCC....

ECBCBB..

DCBCDB..

DCCC.B..

D.B.ABAA

D.BBBB.A

DDDDAD.A

E...AAAA

EEEEEE..

後擺放的圖片會覆蓋前面圖片的字母。所以這張圖片的擺放順序可以為（EDABC）
現在給你一副已經擺好的圖片，問你這幅圖片是有哪些字母，按照怎樣的順序排出來的。按照字典序輸出所有順序。

解題思路：

題目主要是要建圖，首先可以在圖上找出每個字母的左上角和右下角坐標，然後每次對其中一個字母搜索，如果在該字母的位置上是其他字母，代表有有一條有向邊。 建完圖之後，就是輸出拓撲排序的所有序列了。（由於圖比較小，這裡直接用DFS做了）

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
int h, w, g[35][35], has[30];
char mp[35][35];
struct node {
    int s, x, z, y;
    void inital() {
        s = z = 100;
        x = y = -1;
    }
}e[35];
void init() {
    mem(g, 0);
    mem(has, 0);
    for (int i = 0; i < 26; i++) e[i].inital();
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin>>mp[i][j];
            if (isalpha(mp[i][j])) {
                int u = mp[i][j] - 'A';
                if (!has[u]) has[u] = 1;
                e[u].s = min(e[u].s, i);
                e[u].z = min(e[u].z, j);
                e[u].x = max(e[u].x, i);
                e[u].y = max(e[u].y, j);
            }
        }
    }
    for (int u = 0; u < 26; u++) if (has[u]) {
        for (int i = e[u].s; i <= e[u].x; i++) {
            int v1 = mp[i][e[u].z] - 'A', v2 = mp[i][e[u].y] - 'A';
            if (v1 != u) g[u][v1] = 1;
            if (v2 != u) g[u][v2] = 1;
        }
        for (int j = e[u].z + 1; j < e[u].y; j++) {
            int v1 = mp[e[u].s][j] - 'A', v2 = mp[e[u].x][j] - 'A';
            if (v1 != u) g[u][v1] = 1;
            if (v2 != u) g[u][v2] = 1;
        }
    }
}
int out[30], n, vis[30];
vector v;
void dfs(int x, int t) {
    if (t == n) {
        for (int i = 0; i < n; i++) printf("%c", out[i] + 'A');
        puts("");
    }
    for (int i = 0; i < n; i++) if (!vis[v[i]]) {
        int ok = 1;
        for (int j = 0; j < t; j++) if (g[v[i]][out[j]]) ok = 0;
        if (ok) {
            out[t] = v[i];
            vis[v[i]] = 1;
            dfs(v[i], t + 1);
            vis[v[i]] = 0;
        }
    }
}
void gao() {
    v.clear();
    for (int i = 0; i < 26; i++) if (has[i]) v.push_back(i);
    n = v.size();
    mem(vis, 0);
    for (int i = 0; i < n; i++) {
        out[0] = v[i];
        vis[v[i]] = 1;
        dfs(v[i], 1);
        vis[v[i]] = 0;
    }
}
int main () {
    while(scanf("%d%d", &h, &w) != EOF) {
        init();
        gao();
    }
    return 0;
}