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

freeCodeCamp Challenge 365 Bucket Fill 3用状态空间 BFS 求解二维网格最少泛洪填充点击数【免费下载链接】freeCodeCampfreeCodeCamp.orgs 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 是一个贯穿三题的递进子系列题目文件玩法Challenge 329: Bucket Fill6a1d9f98e819ed70a0e994db.md给定起点与 new value把起点所在连通区域重涂成新值返回更新后的网格Challenge 363: Bucket Fill 26a26df95efa55a2524399744.md给定网格与目标色每次点击只能把整个区域涂成目标色求最少点击数此时贪心数区域即可Challenge 365: Bucket Fill 3本文6a26df95efa55a2524399746.md点击可以使用任意颜色作为中间步骤求让整盘变成目标色的最少点击数问题定义与输入输出题目原文描述为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 cells 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.即输入是一个二维网格grid每个格子是单字母颜色字符串和一个目标颜色targetColor一次点击作用于某个格子会把该格子以及所有四方向上、下、左、右不含对角线连通的同色区域整体改色改成的颜色不限于目标色可以是任意颜色这是与 Challenge 363 的本质区别后文详述返回值是最少点击次数整数而不是改色后的网格。题目给出的种子函数如下要求学习者补全函数体并返回点击数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 PP 区域(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([r1,c],[r-1,c],[r,c1],[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 即最短路的标准性质也是该解法正确性的核心依据。区域提取迭代式 DFSgetRegion(g, row, col)用显式栈stack.push/pop做四方向深度优先搜索收集与(row, col)同色连通的所有格子返回一个以r,c字符串为元素的Set。这里有两个实现细节值得注意先出栈再校验循环体开头先pop()再依次检查是否已访问 / 越界 / 颜色不符。越界坐标在被压栈时不做过滤而是靠出栈后的r 0 || r rows || c 0 || c cols统一拦截逻辑集中且不易漏判用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;涂成区域自身已有的颜色不产生任何状态变化直接跳过避免无效的自转移。区域根提取getRegionRootsfor (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 329Bucket Fill单层 DFS原地填充并返回新网格考察递归/连通区域基础Challenge 363Bucket Fill 2一次遍历数区域贪心即最优考察约束收窄时最优策略的简化Challenge 365Bucket 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题型常量 28dailyChallengeJs的定义与判断辅助函数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.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

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

相关推荐

SpringBoot+Vue流浪动物救助管理系统全栈开发实战

永磁同步电机直接转矩控制改进仿真模型详解

get-shit-done Node Repair 工作流解析：任务验证失败后的自主修复算子

更多资讯

HyperFrames constellation-hub 蓝图：节点环聚中心的镜头编排与三大收尾变体

Matlab实现PCA与BP神经网络的手写字母识别

从 Borrow One 理解 Rust 生命周期标注：绑定返回引用与参数借用的完整指南

ToolJet Tags 组件完全指南：数组数据驱动的标签渲染与配置详解

skills不是软件，而是前端能力抽象层：Shell+npx+VSCode的轻量级工程范式

48节点配电系统Simulink仿真：从建模到调参全流程解析

今日更新

CopilotKit Vue Demo 与 React Demo 的 Parity 实现指南：路由、运行时端点与交互语义的全框架对齐

Harbor RBAC 实战：db_auth 模式下非管理员用户管理项目成员的完整验证与权限模型解析

STM32平衡车纯平衡程序从拆包到参数整定的完整调试指南

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？