不用栈的洪水填充：把状态机编码进 16 个备用颜色里

📋 概述

Nils Holm 介绍一种不用栈的洪水填充：只要肯牺牲 16 个颜色值，就能把有限状态自动机的状态直接编码进图像像素。每个状态像素记两个方向——左上角箭头指向它的「来源」像素，右下角箭头指向它下一步要试的方向；四方向乘四种下一方向共 16 个状态，正好对应 16 个备用颜色，再加 4 个标记起点的状态（也可用坐标代替）。走不下去就沿来源箭头回溯，回溯到起点即终止。复杂度与递归版同为 O(n)（准确说 O(4n)），扩展到六边形网格或体素空间需要 36 个备用颜色。动机很实在：在只有 7KB 程序内存、30 层子程序嵌套的 BASIC 系统上写文字版扫雷。