图论之拓扑排序 poj1128 Frame Stacking
题目网址 http://poj.org/problem?id=1128
思路：遍历找出每一种字母出现的最大和最小的横纵坐标，假如本应出现字母A的地方出现了字母B，那么A一定在字母B之前，这就相当于点A到点B有一条有向边，这样就可以建立一张图进行拓扑排序（拓扑排序不唯一，这里题目还要求输出所有结果，这里就进行简单的深度优先搜索）。
#include<cstdio> #include<cstring> using namespace std; struct point { int maxi,maxj,mini,minj; } a[26]; //记录一种字母出现的最大最小坐标 int n,m; int mark[26]; //记录哪些字母出现过 char map[35][35]; //记录原始地图 int in[27]; //记录每种字母的入度 int rec[27][27]; //临接矩阵记录边 int num[26]; //记录答案 int depth; //记录搜索的深度 void init() //寻找每种字母出现的最大最小坐标 { for(int i=0; i<26; i++) if(mark[i]==1) { int max_i=-1,max_j=-1,min_i=10000,min_j=10000; for(int j=0; j<n; j++) for(int k=0; k<m; k++) if(map[j][k]-'A'==i) { if(max_i<j) max_i=j; if(min_i>j) min_i=j; if(max_j<k) max_j=k; if(min_j>k) min_j=k; } a[i].maxi=max_i; a[i].maxj=max_j; a[i].mini=min_i; a[i].minj=min_j; } return ; } void check() //记录边 { for(int i=0; i<n; i++) if(mark[i]) { for(int j=a[i].mini; j<=a[i].maxi; j++) { if(map[j][a[i].maxj]!=i+'A') if(rec[map[j][a[i].maxj]-'A'][i]==0) { rec[map[j][a[i].maxj]-'A'][i]=1; in[map[j][a[i].maxj]-'A']++; } if(map[j][a[i].minj]!=i+'A') if(rec[map[j][a[i].minj]-'A'][i]==0) { rec[map[j][a[i].minj]-'A'][i]=1; in[map[j][a[i].minj]-'A']++; } } for(int j=a[i].minj; j<=a[i].maxj; j++) { if(map[a[i].maxi][j]!=i+'A') if(rec[map[a[i].maxi][j]-'A'][i]==0) { rec[map[a[i].maxi][j]-'A'][i]=1; in[map[a[i].maxi][j]-'A']++; } if(map[a[i].mini][j]!=i+'A') if(rec[map[a[i].mini][j]-'A'][i]==0) { rec[map[a[i].mini][j]-'A'][i]=1; in[map[a[i].mini][j]-'A']++; } } } return ; } void print_num(int Cout) //输出答案 { for(int i=0; i<Cout; i++) printf("%c",num[i]+'A'); puts(""); } void topo_sort(int Cout) //拓扑加深搜 { if(depth==Cout) { print_num(Cout); return ; } for(int i=0; i<26; i++) if(in[i]==0&&mark[i]) { num[depth]=i; depth++; in[i]=-1; for (int k = 0; k < 26; k++) { if (rec[k][i]==1) { in[k]--; } } topo_sort(Cout); for (int k = 0; k < 26; k++) { if (rec[k][i] == 1) { in[k]++; } } in[i]=0; depth--; } return ; } int main() { while(~scanf("%d%d",&n,&m)) { getchar(); memset(in,0,sizeof(in)); //初始化 memset(rec,0,sizeof(rec)); memset(map,0,sizeof(map)); memset(mark,0,sizeof(mark)); memset(num,0,sizeof(num)); for(int i=0; i<n; i++) gets(map[i]); for(int i=0; i<n; i++) for(int j=0; j<m; j++) mark[map[i][j]-'A']=1; init(); check(); int Cout=0; depth=0; for(int i=0; i<26; i++) //计算一共出现了几个字母 if(mark[i])Cout++; topo_sort(Cout); } return 0; }
