看下面的五张 9 x 8 的图像：
........ ........ ........ ........ .CCC....
EEEEEE.. ........ ........ ..BBBB.. .C.C....
E....E.. DDDDDD.. ........ ..B..B.. .C.C....
E....E.. D....D.. ........ ..B..B.. .CCC....
E....E.. D....D.. ....AAAA ..B..B.. ........
E....E.. D....D.. ....A..A ..BBBB.. ........
E....E.. DDDDDD.. ....A..A ........ ........
E....E.. ........ ....AAAA ........ ........
EEEEEE.. ........ ........ ........ ........
1 2 3 4 5
现在，把这些图像按照 1—5 的编号从下到上重叠，第 1 张在最下面，第 5 张在最顶端。如果一张图像覆盖了另外一张图像，那么底下的图像的一部分就变得不可见了。我们得到下面的图像：
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
对于这样一张图像，计算构成这张图像的矩形图像从底部到顶端堆叠的顺序。
下面是这道题目的规则：
* 矩形的边的宽度为 1 ，每条边的长度都不小于 3 。
* 矩形的每条边中，至少有一部分是可见的。注意，一个角同时属于两条边。
* 矩形用大写字母表示，并且每个矩形的表示符号都不相同。
格式
PROGRAM NAME：frameup
INPUT FORMAT：(file frameup.in)
第一行 两个用空格分开的整数：图像高 H (3 <= H <=30) 和图像宽 W (3 <= W <= 30) 。
第二行到第 H+1 行 H 行，每行 W 个字母。
OUTPUT FORMAT：(file frameup.out)
按照自底向上的顺序输出字母。如果有不止一种情况，按照字典顺序输出每一种情况（至少会有一种合法的顺序）。
SAMPLE INPUT
9 8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
SAMPLE OUTPUT
EDABC
分析：
首先，把每个矩形的上下左右边界统统记录下来。这样，沿每一个矩形的边走一遍，就可以知道谁压着它了。用一个数组cover记录谁压着谁。其实就是个有向无回路图。
然后，拓扑排序。因为是要的所有解，所以要回溯法全找出来。
计算拓扑序列时有两种方法：
1.“删点法”，每次删去一个入度为0的点和它出发的所有边。删点的顺序就是一个拓扑序列。
2.把有向图中所有的边反过来，再DFS，遍历完一个结点的子树后输出这个点。不过有个缺点，就是题目要求按字母顺序输出所有解，但这种方法最后还要排序。(我选择的第一种)
【参考程序】：
/*
ID: XIONGNA1
PROG: frameup
LANG: C++
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int up[40],down[40],left[40],right[40];
int f[40],into[40],ans[40];
bool bo[40],cover[40][40];
char a[40][40];
int h,w,num;
void tuopsort(int k)
{
if (k==num+1)
{
for (int i=1;i<=num;i++)
printf("%c",char(ans[i]+64));
printf("\n"); return ;
}
for (int i=1;i<=num;i++)
if (into[i]==0)
{
into[i]=32767; ans[k]=f[i];
for (int j=1;j<=num;j++)
if (cover[f[j]][f[i]]) into[j]--;
tuopsort(k+1);
into[i]=0;
for (int j=1;j<=num;j++)
if (cover[f[j]][f[i]]) into[j]++;
}
}
int main()
{
freopen("frameup.in","r",stdin);
freopen("frameup.out","w",stdout);
scanf("%d%d",&h,&w); getchar();
memset(up,0x7F,sizeof(up));
memset(left,0x7F,sizeof(left));
memset(down,0,sizeof(down));
memset(right,0,sizeof(right));
memset(bo,false,sizeof(bo));
int k;
for (int i=1;i<=h;i++)
{
for (int j=1;j<=w;j++)
{
scanf("%c",&a[i][j]);
if (a[i][j]=='.') continue;
k=(a[i][j]-64); bo[k]=true;
if (i<up[k]) up[k]=i;
if (i>down[k]) down[k]=i;
if (j<left[k]) left[k]=j;
if (j>right[k]) right[k]=j;
}
getchar();
}
memset(cover,false,sizeof(cover));
num=0;
for (int c=1;c<=26;c++)
if (bo[c])
{
num++; f[num]=c;
for (int i=up[c];i<=down[c];i++)
{
if ((a[i][left[c]]-64)!=c)
cover[a[i][left[c]]-64][c]=true;
if ((a[i][right[c]]-64)!=c)
cover[a[i][right[c]]-64][c]=true;
}
for (int i=left[c];i<=right[c];i++)
{
if ((a[up[c]][i]-64)!=c)
cover[a[up[c]][i]-64][c]=true;
if ((a[down[c]][i]-64)!=c)
cover[a[down[c]][i]-64][c]=true;
}
}
memset(into,0,sizeof(into));
for (int i=1;i<=num;i++)
for (int j=1;j<=num;j++)
if (cover[f[i]][f[j]]) into[i]++;
tuopsort(1);
return 0;
}