Consider the following five picture frames shown on an 9 x 8 array:
........ ........ ........ ........ .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
Now place all five picture frames on top of one another starting with 1 at the bottom and ending up with 5 on top. If any part of a frame covers another frame, it hides that part of the frame below. Viewing the stack of five frames we see the following.
.CCC...
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
Given a picture like this, determine the order of the frames stacked from bottom to top.
Here are the rules for this challenge:
| Line 1: | Two space-separated integers: the height H (3 <= H <=30) and the width W (3 <= W <= 30). |
| Line 2..H+1: | H lines, each with a string W characters wide. |
9 8 .CCC.... ECBCBB.. DCBCDB.. DCCC.B.. D.B.ABAA D.BBBB.A DDDDAD.A E...AAAA EEEEEE..
Print the letters of the frames in the order they were stacked from bottom to top. If there are multiple possibilities for an ordering, list all such possibilities -- in alphabetical order -- on successive lines. There will always be at least one legal ordering.
EDABC
看下面的五张 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..
对于这样一张图像，计算构成这张图像的矩形图像从底部到顶端堆叠的顺序。
下面是这道题目的规则：
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)
按照自底向上的顺序输出字母。如果有不止一种情况，按照字典顺序输出每一种情况（至少会有一种合法的顺序）。
9 8 .CCC.... ECBCBB.. DCBCDB.. DCCC.B.. D.B.ABAA D.BBBB.A DDDDAD.A E...AAAA EEEEEE..
EDABC
序言：这道题的完结，预示着我的第四版旅程宣告结束！！
刚看到题目后，我就直接想到了类似于搜索的算法，每次去寻找”浮在最上面“的某个字母并继续搜索。但是我后来发现这样实现起来有点困难，因为没有特别的规划性。后来我就想到了拓扑。如果在某个字符A的边上找到了B,那么就从B向A连一条边。每次寻找入度为0的字母并释放该字母在其他字母上方的痕迹。
需要注意的是，输出时要把所有情况按字典序全部打印。因为拓扑与打印顺序相反，我本来以为拓扑时每次从Z枚举至A就会一定有序，后来发现有点问题。最后，我还是用了排序。
------太囧了！原来最后个点选排超时，结果快排只需0.19s。
代码：
{
PROG:frameup
ID:juan1973
LANG:PASCAL
}
uses math;
var
hang1,hang2,lie1,lie2,num:array[‘A‘..‘Z‘] of longint;
i,j,m,n,cnt,ans_num:longint;
map:array[‘A‘..‘Z‘,‘A‘..‘Z‘] of boolean;
c,t1,t2:char;
a:array[0..35,0..35] of char;
ans:array[1..26] of char;
print:array[1..6000] of string;
t:string;
procedure find(k:longint);
var
c,d:char;
temp:array[‘A‘..‘Z‘] of boolean;
i:longint;
begin
if (k=0) then
begin
inc(ans_num);
for i:=1 to cnt do
print[ans_num]:=print[ans_num]+ans[i];
exit;
end;
for c:=‘Z‘ downto ‘A‘ do
if (hang2[c]>0) and (num[c]=0) then
begin
fillchar(temp,sizeof(temp),0);
for d:=‘A‘ to ‘Z‘ do
if (map[c][d]) then
begin
map[c][d]:=false;
dec(num[d]);
temp[d]:=true;
end;
num[c]:=-1;
ans[k]:=c;
find(k-1);
num[c]:=0;
for d:=‘A‘ to ‘Z‘ do
if (temp[d]) then
begin
map[c][d]:=true;
inc(num[d]);
end;
end;
end;
procedure sort(l,r: longint);
var
i,j:longint;
y,x:string;
begin
i:=l;
j:=r;
x:=print[(l+r) div 2];
repeat
while print[i]<x do
inc(i);
while x<print[j] do
dec(j);
if not(i>j) then
begin
y:=print[i];
print[i]:=print[j];
print[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
begin
assign(input,‘frameup.in‘);
assign(output,‘frameup.out‘);
reset(input);
rewrite(output);
readln(n,m);
fillchar(hang1,sizeof(hang1),$7f);
fillchar(hang2,sizeof(hang2),0);
fillchar(lie1,sizeof(lie1),$7f);
fillchar(lie2,sizeof(lie2),0);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(a[i][j]);c:=a[i][j];
if (c=‘.‘) then continue;
hang1[c]:=min(hang1[c],i);
hang2[c]:=max(hang2[c],i);
lie1[c]:=min(lie1[c],j);
lie2[c]:=max(lie2[c],j);
end;
readln;
end;
for c:=‘A‘ to ‘Z‘ do
if (hang2[c]>0) then
begin
for j:=lie1[c] to lie2[c] do
begin
t1:=a[hang1[c]][j];t2:=a[hang2[c]][j];
if (t1<>‘.‘) and (t1<>c) and not(map[t1][c]) then
begin
map[t1][c]:=true;
inc(num[c]);
end;
if (t2<>‘.‘) and (t2<>c) and not(map[t2][c]) then
begin
map[t2][c]:=true;
inc(num[c]);
end;
end;
for i:=hang1[c]+1 to hang2[c]-1 do
begin
t1:=a[i][lie1[c]];t2:=a[i][lie2[c]];
if (t1<>‘.‘) and (t1<>c) and not(map[t1][c]) then
begin
map[t1][c]:=true;
inc(num[c]);
end;
if (t2<>‘.‘) and (t2<>c) and not(map[t2][c]) then
begin
map[t2][c]:=true;
inc(num[c]);
end;
end;
cnt:=cnt+1;
end;
find(cnt);
sort(1,ans_num);
for i:=1 to ans_num do
writeln(print[i]);
close(input);
close(output);
end.
usaco training 4.4.3 Frame Up 题解,布布扣,bubuko.com
usaco training 4.4.3 Frame Up 题解
原文：http://blog.csdn.net/jiangshibiao/article/details/20370505