poj1128:http://poj.org/problem?id=1128
题意：一个二维图里面有几个相框（四条边的空心矩形框）。有重叠，求重叠顺序。还有题目保证至少存在一种符合要求的序列，当有多种情况时按字典序由小到大输出所有的情况。
题解：建图然后+topsort+dfs ，建图很麻烦的，要细心处理。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 #include <iterator>//stl迭代器 7 using namespace std; 8 char map[32][32];//记录原图 9 int g[27][27];//topsort的图 10 int counts[27];//记录入度 11 int n,m，num;// 行和列 以及出现过的字母的个数 12 bool visit[27];//记录出现过的字母 13 vector<char> ans;//记录结果 14 struct Node{ 15 int x1,y1; 16 int x2,y2; 17 }edge[27];//储存每个节点出现的最左，最右，最上，最下的坐标。 18 void init(){ 19 num=0;//初始化 20 memset(g,0,sizeof(g)); 21 memset(map,0,sizeof(map)); 22 for(int i=1;i<=26;i++){ 23 counts[i]=0; 24 visit[i]=false; 25 edge[i].x1=edge[i].y1=100; 26 edge[i].x2=edge[i].y2=-100; 27 } 28 } 29 void build1(){//建图 30 for(int i=1;i<=n;i++) 31 for(int j=1;j<=m;j++){ 32 cin>>map[i][j]; 33 if(map[i][j]!='.'){ 34 if(!visit[map[i][j]-'A'+1]){ 35 num++; 36 visit[map[i][j]-'A'+1]=true; 37 }//统计出现过的字母 38 if(edge[map[i][j]-'A'+1].x1>i){ 39 edge[map[i][j]-'A'+1].x1=i; 40 } 41 if(edge[map[i][j]-'A'+1].y1>j){ 42 edge[map[i][j]-'A'+1].y1=j; 43 } 44 if(edge[map[i][j]-'A'+1].x2<i){ 45 edge[map[i][j]-'A'+1].x2=i; 46 } 47 if(edge[map[i][j]-'A'+1].y2<j){ 48 edge[map[i][j]-'A'+1].y2=j; 49 }//不断更新各个图片的上下左右的值 50 51 } 52 } 53 } 54 void build2(){//开始建topsort的图g 55 for(int i=1;i<=26;i++){ 56 if(visit[i]){//如果出现过 57 for(int j=edge[i].y1;j<=edge[i].y2;j++){//遍历第一行（最上面的一行）找出与该图不同的图，如果不同 58 if(map[edge[i].x1][j]!=i+'A'-1&&!g[i][map[edge[i].x1][j]-'A'+1]){ 59 g[i][map[edge[i].x1][j]-'A'+1]=1;//如果没有建边，而且满足覆盖关系 60 counts[map[edge[i].x1][j]-'A'+1]++; 61 } 62 } 63 for(int j=edge[i].y1;j<=edge[i].y2;j++){//最下面的一行 64 if(map[edge[i].x2][j]!=i+'A'-1&&!g[i][map[edge[i].x2][j]-'A'+1]){ 65 g[i][map[edge[i].x2][j]-'A'+1]=1; 66 counts[map[edge[i].x2][j]-'A'+1]++; 67 } 68 } 69 for(int j=edge[i].x1;j<=edge[i].x2;j++){//最左边的一列 70 if(map[j][edge[i].y1]!=i+'A'-1&&!g[i][map[j][edge[i].y1 ]-'A'+1]){ 71 g[i][map[j][edge[i].y1]-'A'+1]=1; 72 counts[map[j][edge[i].y1]-'A'+1]++; 73 } 74 } 75 for(int j=edge[i].x1;j<=edge[i].x2;j++){//最右边的一列 76 if(map[j][edge[i].y2]!=i+'A'-1&&!g[i][map[j][edge[i].y2]-'A'+1]){ 77 g[i][map[j][edge[i].y2]-'A'+1]=1; 78 counts[map[j][edge[i].y2]-'A'+1]++; 79 } 80 } 81 } 82 } 83 } 84 void topo(int depth, int count){//排序,depth记录已经处理的字符的个数，count为总的字符个数 85 86 if (depth >= count){//达到开始值就开始输出 87 copy(ans.begin(), ans.end(), ostream_iterator<char>(cout)); 88 cout << endl; 89 return; 90 }// 91 for (int i = 1; i <=26; ++i){ 92 if(visit[i]){ 93 if (counts[i] == 0){ 94 ans.push_back(i+'A'-1); 95 counts[i] = -1; 96 for (int k = 1; k <=26; ++k){ 97 if (g[i][k] == 1){ 98 counts[k]--; 99 } 100 } 101 //递归向下 102 topo(depth+1, count); 103 ans.pop_back();//恢复现场1是ans里面的值要删除，2是各个点的入度要恢复+1； 104 counts[i] = 0; 105 for (int k = 1; k <=26; ++k){ 106 if (g[i][k] == 1){ 107 counts[k]++; 108 } 109 } 110 } 111 } 112 } 113 } 114 int main(){ 115 while(~scanf("%d%d",&n,&m)){ 116 init(); 117 ans.clear();//清除 118 build1(); 119 build2(); 120 topo(0,num);//从0开始 121 } 122 }