要塞

来自计算思维百科
跳转至: 导航搜索
要塞1.jpg

中世纪时,为了更好地守护和保护更多领地,城和要塞都具有多层城墙。偏执狂领主建筑的Strawgoh要塞达到了这种建筑模式的极致。下图是此要塞的结构图,巨大的圆形外墙包含着若干个圆形内墙,所有城墙均设有城门。因此,要想进出,必须使用梯子,在要塞内部从某地移动到另一地也需要耗费大量时间。为此,领主决定挖几条地道将来往不便的地方连接起来。为了设置合适的建设计划,需要找出中间间隔的城墙数最多的两个点,使得地道穿过的城墙数最多。例如下图中的两个星号表示的区域相隔了5层城墙。

要塞2.png

解决方案-转换成树结构

此题看起来与树结构并无太大关系,不过,由“所有城墙不会相交或相接”可知,城墙由层级结构组成。因此,可以把城墙间的包含关系表示成树结构求解。

先给各个城墙围成的区域编号,如下图所示:

要塞3.png

当一个区域包含另一个区域时,连接两个区域,通过这种连接就能把包含关系表示为树结构。

要塞4.png

生成树结构后,从一个区域移动到相邻其他区域的过程将对应于树结构中沿着树的边从一个节点移动到另一节点的过程。因此,往来于两个区域间要经过的最多城墙个数就能变换成在树结构中寻找相隔最远的两个节点的问题。从上图中可以很容易看出区域0到3之间经过的城墙数最多。

运用的计算思维

在图表示的问题中如果找不到解决的思路,不妨利用包含关系将图转化成树结构,使得答案一目了然,运用的是转化的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015