问题场景 #

假设我们有一个 n*m 的二维数组当作画布，画布上有一些已被占用的坐标点（记为 startingPoints）。现在要算出画布里那些没法从外部通过四向（上下左右）Flood Fill填充的点的数量。这里的点分为三类：

• Free：空闲状态，可被填充
• Fielded：已经被填充的点
• Used：已占用点，既不能被填充，也会阻挡填充的路径

计算核心公式 #

其实不用绕弯子，直接通过总点数减去可填充点数，再减去已占用点数就能得到结果：

不可填充点数 = n*m - 可填充点数 - len(startingPoints)

我的实现方案（栈式四向Flood Fill） #

我目前是从画布的所有边界点出发，用栈来实现Flood Fill并统计数据，步骤大概是这样：

1. 先准备一个和原画布同尺寸的状态标记数组，把所有startingPoints对应的位置标记为Used，其余初始为Free
2. 找出画布所有的边界点——也就是行号是0或n-1，或者列号是0或m-1的点，把其中状态为Free的点全部推入栈，同时标记为Fielded，并初始化可填充点数为这些点的数量
3. 开始处理栈：
   • 弹出栈顶的点，检查它的上下左右四个相邻位置
   • 如果相邻点在画布范围内，且状态还是Free，就把它标记为Fielded，可填充点数加1，然后把这个点推入栈
4. 等栈处理完，把得到的可填充点数代入上面的公式，就能算出无法填充的点数量了

内容的提问来源于stack exchange，提问作者user7558351