考察：拓扑排序+dfs
我觉得这道题最难的是理解题目...
这道题的字母是随机使用,不一定按顺序
思路：
我们先要在相片中找到各字母的边框.这里只能暴力查找.找到后遍历边框如果边框不是该字母,说明此字母是下面的边框.利用拓扑排序加边即可.
比较难的点是dfs遍历拓扑排序.本蒟蒻是看了别人的dfs才写出来.总之也和bfs差不多.我们必须先找到无根节点的结点.然后删去与它有关的边.再dfs寻找下一个无根的结点
1 #include <iostream>
2 using namespace std;
3 const int N = 910;
4 int hx,w;
5 bool vis[28];
6 char mp[35][35];
7 int h[N],e[N],ne[N],d[N],idx,n,m,xmp[35][35],cnt,path[28];
8 struct alp{
9 int x1,y1,x2,y2;
10 bool use;
11 }alpha[30];
12 void inits()
13 {
14 fill(d,d+N,0); fill(h,h+N,-1);
15 idx = 0; cnt = 0;
16 fill(vis,vis+28,0);
17 for(int i=1;i<=26;i++) alpha[i].use=0,alpha[i].x1=N,alpha[i].y1=N,alpha[i].y2=0,alpha[i].x2=0;
18 }
19 void add(int a,int b)
20 {
21 e[idx]=b,ne[idx]=h[a],h[a]=idx++; d[b]++;
22 }
23 void dfs(int k)
24 {
25 if(k==cnt){
26 for(int i=0;i<k;i++) printf("%c",path[i]+'A'-1);
27 printf("\n");
28 }else{
29 for(int i=1;i<=26;i++){
30 if(!d[i]&&!vis[i]&&alpha[i].use)
31 {
32 path[k]=i;
33 for(int j=h[i];j!=-1;j=ne[j]) d[e[j]]--;
34 vis[i]=1;
35 dfs(k+1);
36 vis[i]=0;
37 for(int j=h[i];j!=-1;j=ne[j]) d[e[j]]++;
38 }
39 }
40 }
41 }
42 int main()
43 {
44 while(scanf("%d%d",&hx,&w)!=EOF)
45 {
46 inits();
47 for(int i=1;i<=hx;i++){
48 for(int j=1;j<=w;j++){
49 cin>>mp[i][j];
50 if(mp[i][j]!='.') {
51 xmp[i][j]=mp[i][j]-'A'+1;
52 alpha[xmp[i][j]].x1 = min(alpha[xmp[i][j]].x1,i);
53 alpha[xmp[i][j]].y1 = min(alpha[xmp[i][j]].y1,j);
54 alpha[xmp[i][j]].x2 = max(alpha[xmp[i][j]].x2,i);
55 alpha[xmp[i][j]].y2 = max(alpha[xmp[i][j]].y2,j);
56 alpha[xmp[i][j]].use = true;
57 }
58 }
59 }//题目中每个字母都有可能出现,但不是按顺序的
60 for(int i=1;i<=26;i++){
61 if(alpha[i].use){
62 cnt++;
63 for(int j=alpha[i].y1;j<=alpha[i].y2;j++)
64 if(xmp[alpha[i].x1][j]!=i) add(i,xmp[alpha[i].x1][j]);
65 for(int j=alpha[i].y1;j<=alpha[i].y2;j++)
66 if(xmp[alpha[i].x2][j]!=i) add(i,xmp[alpha[i].x2][j]);
67 for(int j=alpha[i].x1;j<=alpha[i].x2;j++)
68 if(xmp[j][alpha[i].y1]!=i) add(i,xmp[j][alpha[i].y1]);
69 for(int j=alpha[i].x1;j<=alpha[i].x2;j++)
70 if(xmp[j][alpha[i].y2]!=i) add(i,xmp[j][alpha[i].y2]);
71 }
72 }
73 dfs(0);
74 }
75 return 0;
76 }