poj 1128 Frame Stacking

题意： 给出 h*w的图形，要求字母框 自底向上的 叠加顺序，有多种顺序要按字典序全部输出。
一开始没想到思路，后面发现其实只要 构图+拓扑排序 即可。。构图为 如果 一个字母框 的边界上有其他字母，那么就 将 edge[][] 标记为1，同时 将该字母 的入度 in +1，而前面提到的其他字母 判断入度 ，标记为 0,
进行 拓扑排序，即 首先 找到一个 入度为 0 的点，删除，然后 将跟该顶点有边 相连的 顶点入度 -1，继续搜索。。
 
[cpp]  
#include<iostream>  
#include<cstdio>  
#include<string.h>  
#include<cstdlib>  
#include<algorithm>  
using namespace std;  
  
const int maxn=50;  
char map[maxn][maxn];  
char str[maxn];  
int edge[maxn][maxn];  
int in[maxn];  
bool vis[maxn];  
int w,h,num;  
int index;  
  
struct lef_top{  
    int x,y;  
}lt[maxn];  
  
struct rig_bot{  
    int x,y;  
}rb[maxn];  
  
struct String{  
    char s[maxn];  
}ans[1000];  
  
int cmp(String a,String b){  
    return strcmp(a.s,b.s)<0;  
}  
  
void get_bound(){  
  
    memset(lt,0x3f,sizeof(lt));  
    memset(rb,-1,sizeof(rb));  
    //memset(flag,false,sizeof(flag));  
  
    for(int i=0;i<h;i++){  
        for(int j=0;j<w;j++){  
            int tmp=map[i][j]-'A';  
            if(lt[tmp].x>i)lt[tmp].x=i;  
            if(lt[tmp].y>j)lt[tmp].y=j;  
            if(rb[tmp].x<i)rb[tmp].x=i;  
            if(rb[tmp].y<j)rb[tmp].y=j;  
        }  
    }  
  
}  
  
void build_graph(){  
    num=0;  
    for(int k=0;k<26;k++){  
        if(rb[k].x==-1)continue;  
        num++;  
        bool flag=true;  
        for(int i=lt[k].x;i<=rb[k].x;i++){  
            for(int j=lt[k].y;j<=rb[k].y;j++){  
                if(i>lt[k].x && i<rb[k].x && j>lt[k].y && j<rb[k].y)continue;  
                if(map[i][j]=='.')continue;  
                int tmp=map[i][j]-'A';  
                if(!edge[tmp][k] && k!=tmp){  
                    flag=false;  
                    edge[tmp][k]=1;  
                    //printf("%d %d\n",k,tmp);  
                    if(in[k]==-1)in[k]=1;  
                    else in[k]++;  
                    if(in[tmp]==-1){  
                        in[tmp]=0;  
                    }  
                }  
            }  
        }  
        if(flag)in[k]=0;  
    }  
}  
  
void DFS(char *s,int cnt){  
    //puts("+++++++++++++++++");  
    if(cnt==num){  
        for(int i=num-1,j=0;i>=0;i--){  
            ans[index].s[j++]=s[i];  
            //putchar(s[i]);  
        }  
        //putchar(10);  
        ans[index++].s[num]=0;  
        return;  
    }  
    for(int k=25;k>=0;k--){  
        if(in[k]==-1)continue;  
        if(in[k]==0){  
            in[k]=-1;  
            for(int i=0;i<26;i++)if(edge[k][i])in[i]--;  
            s[cnt]=k+'A';  
            DFS(s,cnt+1);  
            in[k]=0;  
            for(int i=0;i<26;i++)if(edge[k][i])in[i]++;  
  
        }  
    }  
}  
  
int main(){  
    while(scanf("%d%d",&h,&w)==2){  
        for(int i=0;i<h;i++){  
            scanf("%s",map[i]);  
        }    www.zzzyk.com
        memset(edge,0,sizeof(edge));  
        memset(in,-1,sizeof(in));  
        memset(str,0,sizeof(str));  
        index=0;  
  
        get_bound();  
        build_graph();  
        //printf("%d\n",num);  
        //for(int i=0;i<26;i++){if(in[i]!=-1)printf("%d ",in[i]);}puts("");  
        DFS(str,0);  
        sort(ans,ans+index,cmp);  
        for(int i=0;i<index;i++)puts(ans[i].s);  
  
    }  
}

补充：软件开发 , C++ ,