二维地图中的低点能否排水,取决于通向边界的整条路径,而不是仅看相邻哪格更低。一个看似低的出口后面仍可能有更高的山脊,把水留在内部。
规则与边界
本例五乘五格子,只允许上下左右连通,边界外可排水。每格的排水高度定义为所有通向边界的路径中,路径最高地面高度的最小值。先从全部边界格开始,按当前排水高度从低到高扩展,邻格候选值为两者中的较大者。
本例记录
每格面积一,所有格子高度都为整数,边界格直接与外界相通。
地面高度 3 2 5 1 3 8 5 3 0 4 9 2 2 1 6 8 4 4 4 8 8 7 6 0 3 最低排水高度 3 2 5 1 3 8 5 3 1 4 9 2 2 1 6 8 4 4 4 8 8 7 6 0 3 可蓄深度 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 总蓄水体积1。
表中编号只标记本例对象,不表示排名或另一组数据中的身份。先确认输入单位与边界约定,再逐步核对中间值。零、空结果和不存在是不同状态,不能因为显示相近就互相替代;分数用精确形式保留,便于重新演算。
复核方法
最终排水高度不得低于地面高度,边界格等于自身高度。两者差值是该格在这套模型下的可蓄深度,格子面积统一为一时,把深度相加得到总体积。不能用整张图的最高点给所有凹地统一加水。
可选一个水位,把不高于水位的格子连起来,检查目标格是否已能连到边界。最低连通水位就是它的排水高度,这提供了独立于扩展算法的复核方式。局部低点只有被较高轮廓围住才会存水,低并不自动意味着有水。
能说明什么
这是静态高度场中的理想蓄水模型,没有降雨速度、渗漏、流动惯性或对角通道。用于游戏地形工具时还需明确地图边界是否真的敞开,封闭边界与本例的答案可能完全不同。
这份记录用于理解明确规则下的游戏机制。改变输入后,结果也应随之重新计算;若操作规则不同,应先把新规则写清再比较。可以从一两个步骤手算开始,找出第一处差异,而不是只对照最后一个数值。全部中间记录都属于当前案例,不能直接当成其他场景的固定答案。
