freeCodeCamp 每日编程挑战解析用 JavaScript 实现 Bucket Fill洪水填充算法【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp本篇技术指南围绕 freeCodeCamp 开源仓库中「Dev Playground」每日编程挑战Daily Coding Challenges的第 329 题Challenge 329: Bucket Fill展开系统讲解二维网格上的洪水填充Flood Fill算法的题目要求、判定规则与官方参考解法并结合仓库源码剖析该挑战在课程体系中的类型定义、测试校验与种子数据机制。读完本文你将掌握 4 方向连通性遍历的 DFS/BFS 两种实现并理解 freeCodeCamp 如何以「同题双语言」的方式组织每日挑战。挑战文件与题目速览本挑战的源文件位于仓库的课程目录curriculum/challenges/english/blocks/daily-coding-challenges-javascript/6a1d9f98e819ed70a0e994db.md该文件使用 freeCodeCamp 挑战的 Markdown 标准结构编写front matter 中challengeType: 28是关键元数据在 packages/shared/src/config/challenge-types.ts 中28被定义为dailyChallengeJsJavaScript 每日挑战与之对应29为dailyChallengePyPython 每日挑战。从同一文件可以确认此类挑战的视图类型viewTypes为classic、提交方式submitTypes为tests即用户通过编写函数并通过断言测试来过关。此外本挑战还拥有一个同 id 的 Python 孪生版本curriculum/challenges/english/blocks/daily-coding-challenges-python/6a1d9f98e819ed70a0e994db.md两者共享同一个挑战 id6a1d9f98e819ed70a0e994db题目内容一致仅目标语言不同。题目描述什么是 Bucket Fill题目的核心要求如下给定一个二维网格2D grid、一个起始位置[row, col]和一个新值new value将起始位置处及其所有「连通」的、与起始位置值相同的单元格替换为新值。单元格之间「连通」的定义是水平或垂直方向上相邻不包括对角线方向。函数需要返回更新后的网格。这与图像处理软件如 Photoshop 的油漆桶工具中的洪水填充Flood Fill完全同构把网格看作像素矩阵把颜色看作单元格的值点击一个起点所有同色且四方向连通的区域都会被一次性替换成新颜色。在题目约定中grid是一个二维数组可以理解为string[][]等类型的矩阵[row, col]是起始单元格的行、列下标从 0 开始newValue是要写入的新值。返回值是原地修改后的同一个网格对象参考解法直接修改并返回原数组。判定规则五组官方测试用例挑战的--hints--部分给出了 5 组断言它们是判定解答是否正确的唯一依据同时也是理解边界行为的最佳样例。下表逐一列出输入、起点、新值与期望输出输入网格起始位置新值期望输出[[R,G],[R,G]][0, 1]B[[R,B],[R,B]][[Y,G,G],[Y,Y,Y],[B,Y,R]][1, 2]B[[B,G,G],[B,B,B],[B,B,R]][[O,O,P],[P,O,O],[P,P,O]][2, 0]R[[O,O,P],[R,O,O],[R,R,O]][[T,T,R,T],[R,T,R,T],[R,T,R,T],[T,T,T,T]][0, 3]Y[[Y,Y,R,Y],[R,Y,R,Y],[R,Y,R,Y],[Y,Y,Y,Y]][[G,B,G,B],[R,B,B,G],[B,G,B,R],[B,G,G,B]][2, 2]G[[G,G,G,B],[R,G,G,G],[B,G,G,R],[B,G,G,B]]这些用例覆盖了多种典型场景用例 12×2 小网格起点在右上角其连通区域包含右侧一列两个G替换后右侧整列变B左侧R保持不变。用例 23×3存在多块同色区域起点[1, 2]处的Y与上方Y、下方Y、左下Y均通过上下左右连通形成一块大的Y连通域并被整体替换为B而左上角孤立的Y[0,0]与右下角R不连通保持不变。用例 3多块同色、被异色隔开P被O分隔为两块起点在左下P只有与之连通的右下P一起被替换为R上方孤立的P不受影响。用例 44×4环状异色包围起点[0, 3]的T连通域覆盖除R分隔带之外的全部T最终只有中间竖排的R保留原色。用例 54×4大区域合并起点[2, 2]的B通过连通扩展将原本不相邻的多块B连接成一个整体替换为G同时部分G因被B连通域吞并而改变。关键洞察是连通性由值相等 四方向相邻共同决定两块值相同的单元格若被异色单元格隔开就属于不同连通域不会被一起替换。官方参考解法递归 DFS挑战文件--solutions--中提供的官方解法如下function bucketFill(grid, [row, col], newValue) { const target grid[row][col]; if (target newValue) return grid; function fill(r, c) { if (r 0 || r grid.length) return; if (c 0 || c grid[0].length) return; if (grid[r][c] ! target) return; grid[r][c] newValue; fill(r - 1, c); fill(r 1, c); fill(r, c - 1); fill(r, c 1); } fill(row, col); return grid; }该解法是标准的**深度优先搜索DFS**实现可以拆解为三个关键步骤记录目标值并处理短路target保存起始单元格的原始值若target newValue说明起点已经是新值整片连通域无需任何改动直接返回原网格。这是一个重要的边界优化——如果缺少这一判断递归会在“值与目标值相同”与“值已被改为新值”之间产生语义冲突导致无限递归或错误填充。边界与值匹配检查递归基fill(r, c)首先检查r、c是否越出网格范围r 0 || r grid.length、c 0 || c grid[0].length再检查当前格的值是否等于target。只有三个条件全部通过才继续处理。染色后向四方向扩散将当前格写为newValue然后依次递归上r-1、下r1、左c-1、右c1四个邻居实现 4 方向连通性遍历。注意这里没有对角线邻居符合题目的连通定义。值得注意的实现细节由于单元格在被访问时立即被改写为newValue即染色标记当递归回访到已染色的格子时grid[r][c] ! target会拦截它因此该算法不需要额外的visited布尔矩阵即可避免重复访问与死循环。复杂度分析时间复杂度每个单元格最多被访问一次O(R × C)其中R为行数、C为列数。空间复杂度最坏情况下整个网格都是同一值且全部连通递归深度可达R × C调用栈空间为O(R × C)。对于大网格递归实现可能触发调用栈溢出stack overflow这是 DFS 递归写法的固有局限。进阶实现显式栈 DFS 与 BFS官方解法是递归 DFS但在实际工程中我们常常改用显式栈的迭代 DFS或队列实现的 BFS广度优先搜索以避免深递归带来的栈溢出风险。两者都能得到完全相同的输出。迭代 DFS显式栈function bucketFill(grid, [row, col], newValue) { const target grid[row][col]; if (target newValue) return grid; const rows grid.length; const cols grid[0].length; const stack [[row, col]]; while (stack.length 0) { const [r, c] stack.pop(); if (r 0 || r rows || c 0 || c cols) continue; if (grid[r][c] ! target) continue; grid[r][c] newValue; stack.push([r - 1, c], [r 1, c], [r, c - 1], [r, c 1]); } return grid; }BFS队列function bucketFill(grid, [row, col], newValue) { const target grid[row][col]; if (target newValue) return grid; const rows grid.length; const cols grid[0].length; const queue [[row, col]]; while (queue.length 0) { const [r, c] queue.shift(); if (r 0 || r rows || c 0 || c cols) continue; if (grid[r][c] ! target) continue; grid[r][c] newValue; queue.push([r - 1, c], [r 1, c], [r, c - 1], [r, c 1]); } return grid; }两种实现与官方解法的语义完全一致以target为匹配基准、染色即标记、四方向扩散。区别仅在于遍历顺序深度优先 vs 广度优先最终填充的连通域完全相同。BFS 由于不依赖调用栈空间复杂度在最坏情况下为O(R × C)的队列占用但不存在栈溢出风险。从源码看挑战在仓库中的组织方式挑战类型与视图配置如前所述challengeType: 28映射到 packages/shared/src/config/challenge-types.ts 中的dailyChallengeJs。该模块还提供了两个辅助函数getIsDailyCodingChallenge(challengeType)判断某挑战是否为每日挑战类型涵盖 JS 与 Python 两种getDailyCodingChallengeLanguage(challengeType)返回javascript或python用于确定挑战的作答语言。挑战块Block元数据本挑战所属的课程块定义在 curriculum/structure/blocks/daily-coding-challenges-javascript.json 中其中值得关注的关键字段isUpcomingChange: true该块属于「即将上线」的内容需要在SHOW_UPCOMING_CHANGES环境变量开启时才会出现在课程数据中usesMultifileEditor: true使用多文件编辑器模式helpCategory: JavaScript帮助分类为 JavaScriptdisableLoopProtectTests: true关闭循环保护相关测试便于编写递归实现blockLayout: legacy-challenge-list使用旧版挑战列表布局。这个 JSON 中的challengeOrder按顺序登记了从 Challenge 1 到 Challenge 329以及后续的全部每日挑战每个条目包含挑战 id 与标题本挑战在其中登记为 Challenge 329: Bucket Fill。同题双语言的自动校验由于每个每日挑战都同时存在 JavaScript 与 Python 两个版本同一 id仓库通过 curriculum/src/test/daily-challenges.test.js 对两者的一致性进行自动化校验。该测试使用 Vitest在SHOW_UPCOMING_CHANGEStrue环境下从dev-playgroundsuperblock 加载全部挑战并断言JS 与 Python 每日挑战的数量都大于 0两个语言的挑战数量相等每个挑战的id、title、description以及tests判定用例数量完全一致。这意味着 Bucket Fill 的题目描述、5 组测试用例在 JS 版6a1d9f98e819ed70a0e994db.mdJS与 Python 版6a1d9f98e819ed70a0e994db.mdPython之间是逐字对齐的任何一侧的改动都会触发测试失败。每日挑战的种子数据流程从 tools/daily-challenges/README.md 可以了解每日挑战如何进入生产数据库复制sample.env为.env、安装依赖、以「显示即将上线变更」的方式启动主客户端便于脚本通过 GraphQL 获取挑战然后进入tools/daily-challenges目录执行pnpm seed-daily-challenges即可把 Dev Playground superblock 下的挑战种子化到freecodecamp数据库的DailyCodingChallenges集合中。前端侧client/src/components/daily-coding-challenge/calendar.tsx 等组件则负责按日期展示这些每日挑战。常见错误与调试要点结合 5 组测试用例与官方解法初学者最容易犯的错误集中在以下几点忘记处理target newValue若新值与起始值相同且没有提前返回DFS 会陷入“目标值匹配”与“已染色”互相矛盾的死循环。始终在入口处短路。对角线误判为连通题目明确只允许水平、垂直相邻。若在递归中加入(r1, c1)等对角线邻居会把本应保留原值的格子错误染色。越界检查顺序错误必须先检查行列下标是否越界再访问grid[r][c]否则对负下标或超长下标取值会得到undefined或抛出错误。比较值与写入值混淆递归中的匹配基准永远是起始位置的原值target而不是已经写入的新值。一旦用newValue作为匹配基准整个连通域判断就会错乱。期望返回新数组而非原网格参考解法是原地修改并返回同一个数组assert.deepEqual对引用和内容都成立若你选择拷贝网格如grid.map(row [...row])也能通过测试但需确保拷贝后同样在拷贝上执行填充并返回它。小结Bucket Fill 是每日编程挑战中极具代表性的图论/矩阵遍历题目它将图像处理中的油漆桶工具抽象为「二维网格 4 方向连通 同值替换」三个要素是练习 DFS、BFS 与连通分量概念的绝佳载体。freeCodeCamp 仓库以challengeType: 28dailyChallengeJs组织此类挑战并提供同 id 的 Python 孪生版本与自动化一致性校验确保双语言题目的严格对齐。掌握官方递归解法的同时理解显式栈与 BFS 的等价变形、边界短路与复杂度权衡可以帮助你在真实面试与工程实践中举一反三。【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考