vijos 1030 重疊的方框

下图为5个放置在9x8 的点阵中的方框图:
vijos 1030 重疊的方框

若将他们按顺序叠放起来.则会有某些框的一部分盖住了另外一个框,遮住一些部分. 
下图是这5个框叠放起来的图形:
vijos 1030 重疊的方框

那么这些方框从下至上叠放的顺序是什么呢?
答案是: EDABC.
你的任务是对于一个给定的方框叠放以后的图形, 找出他们从下至上的叠放顺序.
下面是一些规则:
(1). 方框的边宽度为一个字符,边长不少于3个字符;
(2). 每个方框的4条边都有一部分可见, 一个角代表两条边;
(3). 方框用大写字母了表示, 没有两个方框用相同的字符来表示.

格式

输入格式

前两行每行一个数字,分别表示长、宽。

接下来为框叠起来的图。没有框的地方用'.'表示。

输出格式

输出全部可能情况。

按字典顺序排序。

 

解题思路

大概就是找到边框然后判断在其上面的框,建图,进行带有拓扑排序的DFS

 1 var n,m,i,j,max:Longint;
 2     ch:char;
 3     f:array[0..1,0..1] of longint;
 4     dt:Array[1..26,1..26] of longint;
 5     u,d,l,r,c,w:array[1..26] of longint;
 6     pd:array[1..26] of boolean;
 7 procedure dfs(i,k:longint);//带有拓扑排序的dfs
 8 var j:longint;
 9 begin
10 
11     w[k]:=i;
12     if k=max then
13     begin
14         for j:=1 to max do write(char(w[j]+64));
15         writeln;
16         exit;
17     end;
18     for j:=1 to max do
19 
20       dec(c[j],dt[j,i]);
21 
22     for j:=1 to max do
23         if (c[j]=0) and(not pd[j]) then
24         begin
25             pd[j]:=true;
26 
27             dfs(j,k+1);
28             pd[j]:=false;
29         end;
30         for j:=1 to max do
31         inc(c[j],dt[j,i]);
32 
33 end;
34 
35 procedure init;
36 var i,j:longint;
37 begin
38     readln(n,m);//读数
39     for i:=1 to n do
40     begin
41         for j:=1 to m do
42         begin
43             read(ch);
44             if ch='.' then f[i,j]:=0;
45             if ch in['A'..'Z'] then f[i,j]:=ord(ch)-64;
46             if f[i,j]>max then max:=f[i,j];
47         end;
48         readln;
49     end;
50     filldword(u,length(u),1);
51     filldword(l,length(l),1);
52     for i:=1 to n do//寻找左右上下边界
53         for j:=1 to m do
54         if f[i,j]<>0 then
55         begin
56             if u[f[i,j]]>i then u[f[i,j]]:=i;
57             if l[f[i,j]]>j then l[f[i,j]]:=j;
58             if r[f[i,j]]<j then r[f[i,j]]:=j;
59             if d[f[i,j]]<i then d[f[i,j]]:=i;
60         end;
61 
62     {判断方框边界上是否有其他数,如果有,将f[i,j]赋值为1,表示i在j上面,建图}
63     for i:=1 to max do
64     begin
65         for j:=u[i] to d[i] do
66         begin
67             if (f[j,l[i]]<>i)  then dt[f[j,l[i]],i]:=1;
68             if (f[j,r[i]]<>i) then dt[f[j,r[i]],i]:=1;
69         end;
70         for j:=l[i] to r[i] do
71         begin
72             if (f[u[i],j]<>i) then dt[f[u[i],j],i]:=1;
73             if (f[d[i],j]<>i) then dt[f[d[i],j],i]:=1;
74         end;
75     end;
76 end;
77 begin
78     init;
79     for i:=1 to max do//寻找各点出度
80         for j:=1 to max do
81         inc(c[i],dt[i,j]);
82     for i:=1 to max do if c[i]=0 then//出度为0,表示在最下面
83     begin
84       pd[i]:=true;
85       dfs(i,1);
86       pd[i]:=false;
87     end;
88 end.

 

更多相关文章
一周排行