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.

 

更多相关文章
一周排行
  • 幫朋友看新配的电脑,出现奇怪的故障: 看网页.视频什么的都正常,但是玩游戏什么的0分钟就会关机且再次手动开机提示蓝屏代码116. 这时候,可能会想是否是游戏不兼容或显卡驱动什么的 百度116蓝屏,也说驱动有问 ...
  • 题前话(Pre-words) 希望使用Selenium 2.0的人看到这篇文章能够收藏此文,以后遇到该问题,再也不用花费多余的时间进行research了!本文就是对网上所有千奇百怪各种各样的search结果所做的最好 ...
  • 许多网站使用了Google的CDN来加速Jquery之类的库来加速网站访问,但由于方校长发福利的原因,导致这些网站很容易出现无法加载"ajax.googleapis.com"而出现无限循环.今天就 ...
  • hdu26道動態規劃總結
    前言:我们队的dp一直是我在做,说不上做的很顺,有些可以做,有些不能做.到现在为止,做dp ...
  •  jq的ajax完整版本 $.ajax({ url: "GetCityByPId.ashx", data: {pId:pid}, dataType: "JSON", type: ...
  • Android是架构分为三层: 底层      Linux Kernel 中间层  主要由C++实现 (Android 60%源码都是C++实现) 应用层  主要由JAVA开发的应用程序 应用程序执行过程大致如下: ...
  • 


    		    fif私家菜——肉卷
    亲愛的大家们, 好久没有写帖子了,可恶的季节可恶的花粉,耽误了我出名的时间. 周末做了一回
  • 防止aspx木马的IIS SPY变态功能   如果服务器支持aspx语言,而且被上传了aspx木马,利用木马里面的IIS SPY 功能,可以读出IIS里面的所有用户的密码,包括用IIS做FTP的,也能读出所有用户的F ...
  • 


    		    21  單選按鈕(radioButton)
    单选按钮 图片框 选项卡控件 滚动条 进度条 2-
  • log2(5)是無理數
    log2(5)是无理数] 反证法,如果log2(5)是有理数,则可表示为p/q,则2^(p