题意居然还读了好久...
读完题目之后大概就知道拓扑排序了。用拓扑可以求出一些字母之间的关系，谁先，谁后。但是这个关系不是唯一确定的，所以就会产生多种方案（题目还要求按字典序输出所有的方案）
输出方案要麻烦一些，最刚开始还没有想到。可以用一个$dfs$，当这个点的入度变为$0$之后，就输出，递归到下一层，然后再回溯。按字母的字典序枚举就可以输出按字典序排的方案。
/*
ID: Starry21
LANG: C++
TASK: frameup
*/
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define N 35
int h,w,n/*一共n个图像(字母)*/;
char mp[N][N];//存图
int s[N],x[N],z[N],y[N];//每个字母边框的上下左右边在哪一行(列)
char kd[N];//存字母(1~n)
bool vis[N];//各种标记 看地方 vector<int>G[N];//拓扑的边
int ind[N];//入度
char ans[N];
void dfs(int k)
{
//printf("%d\n",k);
if(k>n)
{
for(int i=;i<=n;i++)
printf("%c",ans[i]);
puts("");
return ;
}
for(int i=;i<=n;i++)
if(ind[kd[i]-'A']==&&!vis[i])
{
vis[i]=;
ans[k]=kd[i];
for(int j=;j<G[kd[i]-'A'].size();j++)
{
int v=G[kd[i]-'A'][j];
ind[v]--;
}
dfs(k+);
vis[i]=;
for(int j=;j<G[kd[i]-'A'].size();j++)
{
int v=G[kd[i]-'A'][j];
ind[v]++;
}
}
}
int main()
{
//freopen("frameup.in","r",stdin);
//freopen("frameup.out","w",stdout);
scanf("%d %d",&h,&w);
for(int i=;i<=h;i++)
{
scanf("%s",mp[i]+);
for(int j=;j<=w;j++)
{
if(mp[i][j]=='.') continue;
if(!vis[mp[i][j]-'A'])
{
kd[++n]=mp[i][j];
vis[mp[i][j]-'A']=;
}
if(!s[mp[i][j]-'A']) s[mp[i][j]-'A']=i;
if(!z[mp[i][j]-'A']) z[mp[i][j]-'A']=j;
if(!x[mp[i][j]-'A']) x[mp[i][j]-'A']=i;
if(!y[mp[i][j]-'A']) y[mp[i][j]-'A']=j;
s[mp[i][j]-'A']=min(s[mp[i][j]-'A'],i);
z[mp[i][j]-'A']=min(z[mp[i][j]-'A'],j);
x[mp[i][j]-'A']=max(x[mp[i][j]-'A'],i);
y[mp[i][j]-'A']=max(y[mp[i][j]-'A'],j);
/*
题目保证方块的每一条边都有露出来的
所以直接取min/max就好
*/
}
}
/*for(int i=1;i<=n;i++)
{
printf("%c\n",kd[i]);
int id=kd[i]-'A';
printf("%d %d %d %d\n",s[id],x[id],z[id],y[id]);
}*/
memset(ind,-,sizeof(ind));//排除无关字母
for(int i=;i<=n;i++)
ind[kd[i]-'A']=;
for(int i=;i<=n;i++)//枚举字母
{
memset(vis,,sizeof(vis));//清空 标记这个点连了哪些 不连重边
int id=kd[i]-'A';
for(int j=z[id];j<=y[id];j++)
if(mp[s[id]][j]!=kd[i]&&!vis[mp[s[id]][j]-'A'])
{
G[id].push_back(mp[s[id]][j]-'A');
vis[mp[s[id]][j]-'A']=;
ind[mp[s[id]][j]-'A']++;
}
for(int j=z[id];j<=y[id];j++)
if(mp[x[id]][j]!=kd[i]&&!vis[mp[x[id]][j]-'A'])
{
G[id].push_back(mp[x[id]][j]-'A');
vis[mp[x[id]][j]-'A']=;
ind[mp[x[id]][j]-'A']++;
}
for(int j=s[id];j<=x[id];j++)
if(mp[j][z[id]]!=kd[i]&&!vis[mp[j][z[id]]-'A'])
{
G[id].push_back(mp[j][z[id]]-'A');
vis[mp[j][z[id]]-'A']=;
ind[mp[j][z[id]]-'A']++;
}
for(int j=s[id];j<=x[id];j++)
if(mp[j][y[id]]!=kd[i]&&!vis[mp[j][y[id]]-'A'])
{
G[id].push_back(mp[j][y[id]]-'A');
vis[mp[j][y[id]]-'A']=;
ind[mp[j][y[id]]-'A']++;
}
}
sort(kd+,kd+n+);
memset(vis,,sizeof(vis));
dfs();//按照拓扑排序 入度为0之后可以选也可以不选 题目保证有解
return ;
}
Code