AC_Code:
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 50;
5 const int inf = 0x3f3f3f3f;
6 const int mod = 998244353;
7 #define rep(i,first,second) for(int i=first;i<=second;i++)
8 #define dep(i,first,second) for(int i=first;i>=second;i--)
9
10 char ans[maxn],g[maxn][maxn];
11 int tp[maxn][maxn];
12 int x[maxn],y[maxn],x2[maxn],y2[maxn];
13 int in[maxn],n;
14
15 //(x,y):相应字母的左上角
16 //(x2,y2):相应字母的右下角
17
18 void addTopo(int i,int j,int c){
19 int t=g[i][j]-'A';
20 if( t!=c && !tp[c][t] ){
21 in[t]++;
22 tp[c][t]=1;
23 }
24 }
25
26 void build(){
27 memset(tp,0,sizeof(tp));//tp[i][j] = 1表示有i < j的关系
28 for(int c=n=0;c<26;c++){
29 if(in[c]<0) continue;
30 for(int i=x[c];i<=x2[c];i++){
31 addTopo(i,y[c],c);
32 addTopo(i,y2[c],c);
33 }
34 for(int j=y[c];j<=y2[c];j++){
35 addTopo(x[c],j,c);
36 addTopo(x2[c],j,c);
37 }
38 n++;//统计出现了多少的字符
39 }
40 }
41
42 void topo_dfs(int k){
43 if( k==n ){
44 ans[k]=0;
45 puts(ans);
46 return ;
47 }
48
49 //从前往后找入度为0的点保证以字典序
50 rep(i,0,25){
51 if(in[i]==0){
52 ans[k]=i+'A';
53 in[i]=-1;
54 rep(j,0,25){
55 if( tp[i][j] )
56 in[j]--;
57 }
58
59 topo_dfs(k+1);
60
61 in[i]=0;
62 rep(j,0,25){
63 if( tp[i][j])
64 ++in[j];
65 }
66 }
67 }
68 }
69
70 int main()
71 {
72 int h,w,c;
73 while( ~scanf("%d%d",&h,&w)){
74 rep(i,0,26-1){
75 x[i]=maxn;
76 y[i]=maxn;
77 x2[i]=0;
78 y2[i]=0;
79 }
80 memset(in,-1,sizeof(in));
81 rep(i,0,h-1){
82 scanf("%s",g[i]);
83 rep(j,0,w-1){
84 if( ( c = g[i][j]-'A')<0 )//g[i][j]=='.'
85 continue;
86 if( i<x[c] ) x[c]=i;
87 if( i>x2[c] ) x2[c]=i;
88 if( j<y[c] ) y[c]=j;
89 if( j>y2[c] ) y2[c]=j;
90 in[c]=0;
91 }
92 }
93 build();
94 topo_dfs(0);
95 }
96 return 0;
97 }
参考：这里