POJ1128 Frame Stacking（拓扑排序）

题意：给你一个平面，里面有些矩形（由字母围成），这些矩形互相有覆盖关系，请从求出最底层的矩形到最上层的矩形的序列，如果存在多种序列，答案按照字典序依次输出。

思路：这道题的难点在建图，利用矩形之间的覆盖关系建图，说着容易，实际上仔细想想不太容易。由于矩形的任意一个边界不会完全被覆盖，所以我们可以确定一个矩形的上下左右边界，然后对每个矩形的上下左右边界扫一遍，看是否被其他字母所覆盖，利用覆盖关系建图。这里无法利用队列的方式拓扑排序，因为要输出所有的序列，所以dfs的方式更为出色，具体的注释都写在代码里面了。

//Author: xiaowuga

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

#include <cmath>

#include <cstring>

#include <cstdio>

#include <ctime>

#include <map>

#include <bitset>

#include <cctype>

#define maxx INT_MAX

#define minn INT_MIN

#define inf 0x3f3f3f3f

#define mem(s,ch) memset(s,ch,sizeof(s))

#define da cout<<"da"<<endl

#define uoutput(a,i,l,r) for(int i=l;i<r;i++) if(i==l) cout<<a[i];else cout<<" "<<a[i];cout<<endl;

#define doutput(a,i,l,r) for(int i=r-1;i>=0;i--) if(i==r-1) cout<<a[i];else cout<<" "<<a[i];cout<<endl;

const long long N=;

using namespace std;

typedef long long LL;

int L[N],R[N],U[N],D[N],in[N],vis[N],v[N];

//L左边界数组，R有边界数组，U上边界数组，D下边界数组

//vis字母存在数组，v是dfs中是否访问数组

char pic[N][N],ans[N];

int p[N][N];

int n,m,ct;

//初始化

void init(){

    ct=;//存在字母总数量初始化为0

    mem(in,);//入度数组初始化为0

    mem(vis,);//字母存在数组初始化为0

    mem(v,);

    mem(p,);//邻接矩阵初始化为0

    //上左边界最大化，下右边界最小化

    mem(L,inf);mem(U,inf);mem(R,-);mem(D,-);

}

void make_g(int i,int j,int k){

    int t=pic[i][j]-'A';

    if(k!=t){

        if(!p[k][t]) {p[k][t]=;in[t]++;}

    }

}

void dfs(int x,int y){

    ans[y]=x+'A';

    v[x]=;//标记为访问过

    if(y==ct){//全部字母已经排好拓扑序

        for(int i=;i<=ct;i++) cout<<ans[i];cout<<endl;//输出

        v[x]=;//恢复

        return ;

    }

    int q[N],num=;

    //i从0-26保证了字典序

    for(int i=;i<;i++){

        if(p[x][i]) --in[i];//存在连接则连接减少入度

        if(vis[i]&&!in[i]&&!v[i]) q[num++]=i;//存在连接且入度减为0，且未访问

    }

    //对所有后续节点进行dfs

    for(int i=;i<num;++i) dfs(q[i],y+);

    for(int i=;i<;i++) if(p[x][i]) in[i]++;//恢复

    v[x]=;//恢复

}

void topo(){

    for(int i=;i<;++i) if(vis[i]&&!in[i]) dfs(i,);

}

int main() {

    ios::sync_with_stdio(false);cin.tie();

    while(cin>>n>>m){

        init();

        //输入整个图形并确定每个矩形的上下左右边界

        for(int i=;i<n;++i) for(int j=;j<m;++j){

            cin>>pic[i][j];

            if(pic[i][j]!='.'){

                int t=pic[i][j]-'A';

                if(!vis[t]){ vis[t]=;ct++;}

                L[t]=min(L[t],j);

                R[t]=max(R[t],j);

                U[t]=min(U[t],i);

                D[t]=max(D[t],i);

            }

        }

        for(int k=;k<;k++){

           if(vis[k]){

                int i,j;

                i=U[k];//上边界上

                for(j=L[k];j<=R[k];j++) make_g(i,j,k);

                i=D[k];//下边界上

                for(j=L[k];j<=R[k];j++) make_g(i,j,k);

                j=L[k];//左边界上

                for(i=U[k]+;i<D[k];i++) make_g(i,j,k);

                j=R[k];//右边界上

                for(i=U[k]+;i<D[k];i++) make_g(i,j,k);

           }

        }

        topo();

    }

    return ;

}