一片空格没有挨着地图边缘,并不代表它是封闭洞;它可能通过一条弯曲通道连到外部。由边界空格出发搜索,能把内部空洞与外部可达空地分开。
本篇给出一份完整且可重复的虚构游戏记录。先读清规则,再尝试自行推演输入,最后逐项对照中间状态。不同作品可以选择不同约定,只有在相同前提下才能比较结果;不要只看最终数字相同就认为过程正确。
约定与原始记录
七乘七地图只有墙和空格,移动只允许上下左右。以所有边界空格为入口,能走到的空格都属于外部区域;其他空格才是洞。斜角接触不能穿过,也不自动填充任何格子。
.##.... #..##.# ..###.. ..#.### ..###.. ##..... ...####
逐步计算
第0行地图.##....,外部可达空格横坐标[0, 3, 4, 5, 6],洞格横坐标[]。
第1行地图#..##.#,外部可达空格横坐标[1, 2, 5],洞格横坐标[]。
第2行地图..###..,外部可达空格横坐标[0, 1, 5, 6],洞格横坐标[]。
第3行地图..#.###,外部可达空格横坐标[0, 1],洞格横坐标[3]。
第4行地图..###..,外部可达空格横坐标[0, 1, 5, 6],洞格横坐标[]。
第5行地图##.....,外部可达空格横坐标[2, 3, 4, 5, 6],洞格横坐标[]。
第6行地图...####,外部可达空格横坐标[0, 1, 2],洞格横坐标[]。
洞格(3,3)虽为空格,但上下左右连通分量没有任何地图边界格;不能仅凭斜角相邻把它连到外部。
49格中墙22格,外部空地26格,洞1格,三者不重叠且合计49。
复核方法与适用范围
对每个尚未归类的空格独立找出其整个连通分量;分量里只要有一个边界格,它就属于外部。比较这种逐分量检查与边界同时扩展得到的分类。
本例的墙是占据完整格子的阻挡,不能从两个墙角之间挤过。如果游戏允许斜向移动,洞的定义会发生变化,应先改通行规则再重新计算。分类结果只用于说明拓扑关系,不会自动推断地形高度或水流。
练习时可以只改动一个输入,再观察哪一步首次出现差异。对等于门槛、重复请求、空集合和最后一步分别留一份记录;如果发现异常,应先回到单位、顺序和边界约定,避免用额外补偿掩盖前面已经发生的错误。
