freeCodeCamp Challenge 365 Bucket Fill 3：用状态空间 BFS 求解二维网格最少泛洪填充点击数

freeCodeCamp Challenge 365 Bucket Fill 3：用状态空间 BFS 求解二维网格最少泛洪填充点击数

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp

本篇技术文章围绕 freeCodeCamp 每日编程挑战（Daily Coding Challenges JavaScript）系列的第 365 题——也就是该系列的收官题 "Bucket Fill 3"——展开。你将完整掌握这道题的问题定义、它与前作 Bucket Fill 2 的关键差异、参考解法的 BFS 状态空间搜索实现，以及每一段核心代码（区域提取、状态规范化、去重剪枝）背后的设计动机与复杂度边界，读完后可独立复现并扩展这类"网格变换最少步数"问题。

题目背景：每日挑战系列的第 365 题

该题目定义在课程文件 curriculum/challenges/english/blocks/daily-coding-challenges-javascript/6a26df95efa55a2524399746.md 中，front matter 元数据如下：

--- id: 6a26df95efa55a2524399746 title: "Challenge 365: The Last Challenge: Bucket Fill 3" challengeType: 28 dashedName: challenge-365 ---

其中challengeType: 28对应共享包中的dailyChallengeJs常量，即"每日编程挑战（JavaScript 版）"这一挑战类型，可在 packages/shared/src/config/challenge-types.ts 中确认：

const dailyChallengeJs = 28; const dailyChallengePy = 29;

该文件还导出了getIsDailyCodingChallenge(challengeType)等辅助函数，用于在客户端与服务端识别每日挑战题型。

题目在题库中的位置由区块结构文件 curriculum/structure/blocks/daily-coding-challenges-javascript.json 声明：整个challengeOrder数组从 "Challenge 1: Vowel Balance" 一直排到末尾的：

{ "id": "6a26df95efa55a2524399746", "title": "Challenge 365: The Last Challenge: Bucket Fill 3" }

与题目描述中 "Today marks a year of daily coding challenges. This is the last new one for now." 相呼应——这是该系列的第 365 题，也是当前最后一道新题。区块配置还包含几个与本题运行环境相关的字段：

• "usesMultifileEditor": true：该区块使用多文件编辑器展示；
• "disableLoopProtectTests": true：关闭循环保护测试。这一点值得注意——参考解法使用了while循环和 BFS 队列，若不关闭保护，循环次数限制可能误伤合法解法；
• "helpCategory": "JavaScript"：归类到 JavaScript 帮助分类。

在每日挑战系列内部，Bucket Fill 是一个贯穿三题的递进子系列：

问题定义与输入输出

题目原文描述为：

Given a 2D grid of single-letter color strings and a target color, return the minimum number of flood fill "clicks" needed to make the entire grid that color.

• Each click changes the clicked cell's color and the entire region of connected cells of the same color (4-directional).
• Clicks can use any color as an intermediate step, not just the target color.

即：

1. 输入是一个二维网格grid（每个格子是单字母颜色字符串）和一个目标颜色targetColor；
2. 一次"点击"作用于某个格子，会把该格子以及所有四方向（上、下、左、右，不含对角线）连通的同色区域整体改色；
3. 改成的颜色不限于目标色，可以是任意颜色（这是与 Challenge 363 的本质区别，后文详述）；
4. 返回值是最少点击次数（整数），而不是改色后的网格。

题目给出的种子函数如下，要求学习者补全函数体并返回点击数：

function bucketFill(grid, targetColor) { return grid; }

测试用例（断言）共 6 组，覆盖了"已完成"、"单区域"、"可合并区域"与更大的 4x4、5x4、5x5 网格：

assert.equal(bucketFill([["B", "B"], ["B", "B"]], "R"), 1);

全网格只有一种颜色 B 且目标为 R：整个网格是一个区域，点一次即可，返回1。

assert.equal(bucketFill([["G", "G", "G"], ["G", "G", "G"], ["G", "G", "G"]], "G"), 0);

网格颜色已经等于目标色 G：无需任何操作，返回0。这是"边界情况：初始即完成"的用例。

assert.equal(bucketFill([["P", "P", "Y"], ["Y", "P", "Y"], ["Y", "P", "P"]], "O"), 2);

这个 3x3 网格是理解本题难点的关键用例，手工推演如下：

P P Y Y P Y Y P P

• P 区域：(0,0) (0,1) (1,1) (2,1) (2,2)五个格子经四方向相邻全部连通，构成 1 个区域；
• Y 区域：(0,2) (1,2)相连、(1,0) (2,0)相连，构成 2 个互不连通的区域。

目标色 O 在网格中完全不存在。若按 Challenge 363 的"数区域"贪心思路（每次点击把区域涂成目标色），需要 1 + 2 =3次点击；但本题允许用任意中间色，可以先点一个 Y 区域把它涂成 P（与 P 区域合并，1 次点击），再点合并后的 P 大区域涂成 O（第 2 次点击），总共2次。这直接说明了为什么贪心不再最优、需要搜索。

assert.equal(bucketFill([["G", "Y", "C", "C"], ["Y", "Y", "Y", "B"], ["C", "Y", "B", "B"], ["C", "B", "B", "C"]], "R"), 4);

assert.equal(bucketFill([["G", "G", "O", "O"], ["G", "Y", "B", "Y"], ["B", "Y", "B", "Y"], ["B", "Y", "B", "Y"], ["G", "G", "G", "G"]], "P"), 5);

assert.equal(bucketFill([["R", "G", "R", "G"], ["R", "G", "R", "G"], ["B", "B", "B", "B"], ["B", "B", "B", "B"], ["R", "G", "R", "G"]], "Y"), 3);

最后一个 5x5 棋盘格用例很有代表性：R 与 G 在上下两区交错、B 占据中间两行。若逐区域涂目标色需要 6 + 6 + 1 = 13 次点击，而答案只有3——通过把棋盘格的 R/G 区域两两合并（涂成对方的颜色）再整体涂 Y，点击数被大幅压缩。

为什么贪心不够：从 Bucket Fill 2 到 Bucket Fill 3 的跃迁

回顾 Challenge 363 的参考解法：它用一次 DFS 遍历，凡是未访问且不是目标色的区域就计数加一，clicks即答案。该解法成立的前提是每次点击必须涂成目标色——区域之间无法互相合并，每个区域至少消耗一次点击，且一次点击恰好消掉一个区域，因此区域数就是最优解。

Challenge 365 把约束放宽为"点击可以涂任意颜色"，最优策略变成了有意识地把区域合并：把某个区域涂成相邻区域的颜色，两者合为一个更大的区域，后续可以用一次点击消掉合并后的整体。点击数的下界不再是"区域数"，而是要在"合并哪些区域、按什么顺序合并"的决策空间中寻找最优。这正是把问题从"一次遍历可解"提升为"状态空间搜索"的原因。

参考解法：网格状态上的 BFS 广度优先搜索

题目给出的官方参考解法如下（完整代码，可直接复制到编辑器中运行验证）：

function bucketFill(grid, targetColor) { const rows = grid.length; const cols = grid[0].length; function gridToString(g) { return g.map(r => r.join(",")).join("|"); } function getRegion(g, row, col) { const color = g[row][col]; const visited = new Set(); const stack = [[row, col]]; while (stack.length) { const [r, c] = stack.pop(); const key = `${r},${c}`; if (visited.has(key)) continue; if (r < 0 || r >= rows || c < 0 || c >= cols) continue; if (g[r][c] !== color) continue; visited.add(key); stack.push([r+1,c],[r-1,c],[r,c+1],[r,c-1]); } return visited; } function floodFill(g, row, col, color) { const next = g.map(r => [...r]); const region = getRegion(g, row, col); for (const key of region) { const [r, c] = key.split(",").map(Number); next[r][c] = color; } return next; } function isComplete(g) { return g.every(row => row.every(cell => cell === targetColor)); } function getColors(g) { return [...new Set([...g.flat(), targetColor])]; } function getRegionRoots(g) { const visited = new Set(); const roots = []; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { const key = `${r},${c}`; if (!visited.has(key)) { const region = getRegion(g, r, c); for (const k of region) visited.add(k); roots.push([r, c]); } } } return roots; } const initial = grid.map(r => [...r]); if (isComplete(initial)) return 0; const queue = [[initial, 0]]; const seen = new Set([gridToString(initial)]); while (queue.length) { const [current, clicks] = queue.shift(); const colors = getColors(current); const roots = getRegionRoots(current); for (const [r, c] of roots) { for (const color of colors) { if (color === current[r][c]) continue; const next = floodFill(current, r, c, color); if (isComplete(next)) return clicks + 1; const key = gridToString(next); if (!seen.has(key)) { seen.add(key); queue.push([next, clicks + 1]); } } } } }

下面逐块解析其设计。

状态与转移

• 状态：整张网格的完整快照。BFS 从初始网格initial（深拷贝，避免污染入参）出发，queue中存放[网格快照, 已用点击数]二元组；
• 转移（一次点击）：对当前网格的每一个区域（由getRegionRoots提取的根列表）×每一种候选颜色color，执行一次泛洪填充floodFill，得到新状态，代价恒为 1；
• 目标判断：isComplete(g)检查所有格子是否都等于targetColor，是则返回clicks + 1。

由于 BFS 按点击数逐层展开，第一个到达"全为目标色"状态的路径长度就是最少点击数——这是"单位代价下 BFS 即最短路"的标准性质，也是该解法正确性的核心依据。

区域提取：迭代式 DFS

getRegion(g, row, col)用显式栈（stack.push/pop）做四方向深度优先搜索，收集与(row, col)同色连通的所有格子，返回一个以"r,c"字符串为元素的Set。这里有两个实现细节值得注意：

1. 先出栈再校验：循环体开头先pop()，再依次检查"是否已访问 / 越界 / 颜色不符"。越界坐标在被压栈时不做过滤，而是靠出栈后的r < 0 || r >= rows || c < 0 || c >= cols统一拦截，逻辑集中且不易漏判；
2. 用Set而非递归：Challenge 329 的解法使用递归 DFS 直接原地改写网格；本题因为要对同一张网格反复做"假设性改色"，所以采用迭代栈 + 只读遍历的方式提取区域，再由floodFill在副本上应用修改，保证 BFS 中的状态不可变。

状态规范化与去重

gridToString(g)把网格序列化为形如B,B|B,B的字符串（行内逗号、行间竖线分隔），作为状态的唯一标识。seen集合记录所有已探索过的状态：

const key = gridToString(next); if (!seen.has(key)) { seen.add(key); queue.push([next, clicks + 1]); }

去重在这里承担双重职责：

• 正确性上防止死循环：点击允许涂任意颜色，意味着可以把刚合并的区域又涂回旧色，状态图是带环的；没有seen，搜索会在等价状态间反复打转；
• 性能上剪枝：同一网格快照无论通过哪条路径到达，其后续最优代价相同，只保留第一次入队即可。

候选颜色的选择：getColors 的小心机

function getColors(g) { return [...new Set([...g.flat(), targetColor])]; }

候选颜色集合 = 当前网格中出现过的所有颜色 ∪目标色。把targetColor显式并入是必要的：在"目标色尚未出现在网格中"的情形（如 3x3 用例中目标 O），如果不加入目标色，搜索将永远无法直接执行"把某区域涂成 O"这一步，答案会偏大甚至无解。同时循环内还有一处剪枝：

if (color === current[r][c]) continue;

涂成区域自身已有的颜色不产生任何状态变化，直接跳过，避免无效的自转移。

区域根提取：getRegionRoots

for (const [r, c] of roots) { for (const color of colors) { ... } }

外层枚举的不是格子而是区域：getRegionRoots扫描全网格，每遇到一个未访问格子就取其整个区域、只记录一个代表根[r, c]。同一个区域内任意格子作为点击点效果完全相同，按区域枚举可以把每个状态的转移数从"格子数 × 颜色数"压缩到"区域数 × 颜色数"。

复杂度与适用边界

从源码结构可以推断出该解法的资源消耗特征：

• 状态空间：每个格子最多取"网格中出现过的颜色 + 目标色"中的一种取值，状态数上界为 (颜色数 + 1)^(格子数)，实际可达状态远小于此上界，但随网格尺寸呈指数增长趋势；
• 单步代价：getRegionRoots+ 每个区域的getRegion+ 每次floodFill都是 O(格子数) 量级，因此单个状态展开约为 O(格子数 × 区域数 × 颜色数)；
• 队列实现：queue.shift()在数组头部出队是 O(n) 操作，严格意义上可以换成双端队列，但题目给出的网格最大只有 5x5（约 25 格、4~5 种颜色），题设规模下完全够用。

因此这套"状态 BFS"方案是面向题设小网格的精确解：它保证返回全局最优值，而不是启发式近似。若网格放大到 10x10 以上且颜色更多，就需要换用基于区域邻接图的建模（把区域合并建模为图上的收缩操作）来控制状态爆炸——这是本题解法之外的延伸方向。

与系列前作的对照小结

• Challenge 329（Bucket Fill）：单层 DFS，原地填充并返回新网格，考察递归/连通区域基础；
• Challenge 363（Bucket Fill 2）：一次遍历数区域，贪心即最优，考察"约束收窄时最优策略的简化"；
• Challenge 365（Bucket Fill 3）：状态空间 BFS + 规范化去重 + 区域级转移枚举，考察"约束放宽后最优策略的搜索化"。

三道题共用同一个bucketFill函数名但签名与语义逐级变化（返回网格 → 返回点击数且只能涂目标色 → 返回点击数且可涂任意色），正好构成一条"泛洪填充"主题的完整学习曲线，也与题库中challengeOrder的 329 → 363 → 365 排列顺序一致。

如何在仓库中验证

题目源码与答案都保存在课程 markdown 文件中，可在本地仓库直接查看：

• 本题（含全部 6 组断言、种子代码与参考解法）：curriculum/challenges/english/blocks/daily-coding-challenges-javascript/6a26df95efa55a2524399746.md；
• 区块元数据与 365 题排序：curriculum/structure/blocks/daily-coding-challenges-javascript.json；
• 题型常量 28（dailyChallengeJs）的定义与判断辅助函数：packages/shared/src/config/challenge-types.ts；
• 每日挑战的取题 API 与 seed 工具分别位于 api/src/daily-coding-challenge/ 与 tools/daily-challenges/seed-daily-challenges.ts，可用于理解题目如何被按日分发。

验证方式也很直接：把参考解法粘贴进 Node 环境（或课程编辑器），逐条执行 6 组assert.equal断言，全部通过即说明实现正确；若希望确认"最优性"，可以用 3x3 用例手工构造"先合并后涂目标色"的 2 步序列加以印证。

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp