不用栈的洪泛填充：拿 16 种颜色当状态机
来源：t3x.org — 2023-01
📋 概述
Nils M Holm 的小论文给出一个反直觉的洪泛填充实现：如果图像里能空出 16 个颜色值，就不需要任何栈或其他动态数据结构。做法是把 16 种状态编码进这些颜色——每个像素存两个方向，一个是"原点像素"（我是从哪个邻居被尝试填充的），一个是"下一步该试哪个方向"，于是回溯路径被写进了图像本身。碰到无路可走的状态就填成最终颜色并沿原点箭头退回，最后从起点一路把无方向的状态刷成填充色。算法复杂度仍是线性的 O(4n)，可以推广到六边形网格或体素空间，但那时要 36 个空余颜色。作者说这个变体是为一个只有 7K 程序内存、30 层子程序嵌套的 BASIC 机器上的文字扫雷写的，文末还附了完整的 BASIC 实现。
🔑 核心要点
- 核心洞察是把回溯栈搬进图像本身：16 个空余颜色值编码有限状态机的 16 个状态
- 每个状态像素存两个方向：左上箭头指向原点像素（我是从哪来的），右下箭头是下一步要试的方向
- 回溯规则很朴素：状态里没有方向可试时，当前像素填成最终色，并沿原点箭头退回上一格
- 若还能再空出 4 个值，可以额外标记起点（它没有原点），否则记一个坐标就够了
- 复杂度没有变差：仍是 O(n)，精确说 O(4n)，因为每个像素都要试四个方向
- 推广要加价：六边形网格或体素空间需要 36 个空余颜色；这实现原本是为 7K 内存、30 层嵌套的 BASIC 扫雷写的
💡 金句
这个变体是为一个文字版扫雷游戏写的，那台 BASIC 机器只有 7K 字节程序内存和 30 层子程序嵌套。
👍 0
👎 0
← 返回 Lobsters 首页