poj1128:http://poj.org/problem?id=1128
题意：一个二维图里面有几个相框（四条边的空心矩形框）。有重叠，求重叠顺序。还有题目保证至少存在一种符合要求的序列，当有多种情况时按字典序由小到大输出所有的情况。
题解：建图然后+topsort+dfs ，建图很麻烦的，要细心处理。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include <iterator>//stl迭代器
using namespace std;
char map[][];//记录原图
int g[][];//topsort的图
int counts[];//记录入度
int n,m，num;// 行和列 以及出现过的字母的个数
bool visit[];//记录出现过的字母
vector<char> ans;//记录结果
struct Node{
int x1,y1;
int x2,y2;
}edge[];//储存每个节点出现的最左，最右，最上，最下的坐标。
void init(){
num=;//初始化
memset(g,,sizeof(g));
memset(map,,sizeof(map));
for(int i=;i<=;i++){
counts[i]=;
visit[i]=false;
edge[i].x1=edge[i].y1=;
edge[i].x2=edge[i].y2=-;
}
}
void build1(){//建图
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
cin>>map[i][j];
if(map[i][j]!='.'){
if(!visit[map[i][j]-'A'+]){
num++;
visit[map[i][j]-'A'+]=true;
}//统计出现过的字母
if(edge[map[i][j]-'A'+].x1>i){
edge[map[i][j]-'A'+].x1=i;
}
if(edge[map[i][j]-'A'+].y1>j){
edge[map[i][j]-'A'+].y1=j;
}
if(edge[map[i][j]-'A'+].x2<i){
edge[map[i][j]-'A'+].x2=i;
}
if(edge[map[i][j]-'A'+].y2<j){
edge[map[i][j]-'A'+].y2=j;
}//不断更新各个图片的上下左右的值 }
}
}
void build2(){//开始建topsort的图g
for(int i=;i<=;i++){
if(visit[i]){//如果出现过
for(int j=edge[i].y1;j<=edge[i].y2;j++){//遍历第一行（最上面的一行）找出与该图不同的图，如果不同
if(map[edge[i].x1][j]!=i+'A'-&&!g[i][map[edge[i].x1][j]-'A'+]){
g[i][map[edge[i].x1][j]-'A'+]=;//如果没有建边，而且满足覆盖关系
counts[map[edge[i].x1][j]-'A'+]++;
}
}
for(int j=edge[i].y1;j<=edge[i].y2;j++){//最下面的一行
if(map[edge[i].x2][j]!=i+'A'-&&!g[i][map[edge[i].x2][j]-'A'+]){
g[i][map[edge[i].x2][j]-'A'+]=;
counts[map[edge[i].x2][j]-'A'+]++;
}
}
for(int j=edge[i].x1;j<=edge[i].x2;j++){//最左边的一列
if(map[j][edge[i].y1]!=i+'A'-&&!g[i][map[j][edge[i].y1 ]-'A'+]){
g[i][map[j][edge[i].y1]-'A'+]=;
counts[map[j][edge[i].y1]-'A'+]++;
}
}
for(int j=edge[i].x1;j<=edge[i].x2;j++){//最右边的一列
if(map[j][edge[i].y2]!=i+'A'-&&!g[i][map[j][edge[i].y2]-'A'+]){
g[i][map[j][edge[i].y2]-'A'+]=;
counts[map[j][edge[i].y2]-'A'+]++;
}
}
}
}
}
void topo(int depth, int count){//排序,depth记录已经处理的字符的个数，count为总的字符个数 if (depth >= count){//达到开始值就开始输出
copy(ans.begin(), ans.end(), ostream_iterator<char>(cout));
cout << endl;
return;
}//
for (int i = ; i <=; ++i){
if(visit[i]){
if (counts[i] == ){
ans.push_back(i+'A'-);
counts[i] = -;
for (int k = ; k <=; ++k){
if (g[i][k] == ){
counts[k]--;
}
}
//递归向下
topo(depth+, count);
ans.pop_back();//恢复现场1是ans里面的值要删除，2是各个点的入度要恢复+1；
counts[i] = ;
for (int k = ; k <=; ++k){
if (g[i][k] == ){
counts[k]++;
}
}
}
}
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
ans.clear();//清除
build1();
build2();
topo(,num);//从0开始
}
}