FindingOcean海洋标记算法：airbnb题库BFS与DFS洪水填充方案完整对比

FindingOcean海洋标记算法airbnb题库BFS与DFS洪水填充方案完整对比【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnbairbnb 面试题集中的 FindingOcean 题是图遍历的经典应用给定一张陆地与水域字符地图把起点所在的连通水域整体标记为海洋。本文基于 airbnb 开源题集里的 Java 实现讲透 BFS广度优先搜索与 DFS深度优先搜索两种洪水填充算法的核心原理、优劣对比与选型策略帮新手快速拿下这道高频面试题。 题目背景把水的 “W” 变成海洋的 “O”FindingOcean 原题来自 airbnb 面试输入是一个字符串数组W表示水、L表示陆地再给一个起始坐标指向海洋中的某个位置。任务是把与起点连通的所有水格改成O海洋。“连通”的定义是上下左右 4 方向相邻起点本身是海洋格所有与任一海洋格直接相邻的水格也都是海洋格。官方例子原始地图 从 (0, 1) 洪水填充后 WWWLLLW OOOLLLW WWLLLWW OOLLLWW WLLLLWW OLLLLWW注意右侧那一列水被陆地L挡着不属于同一连通区域所以不会被标记。这就是图论里的“连通分量”问题最通用的解法就是洪水填充。 BFS 实现解析题集里的参考答案题集中的 BFS 方案位于src/main/java/finding_ocean/FindingOcean.java核心思想可以拆成三步起点整数编码用行 * 列数 列这一个整数表示二维坐标省掉额外的点对象入队即染色水格一进队列就立刻从W改成O防止同一个格子被反复入队——这是“入队时访问”的关键技巧四方向扩散每次出队一个格子检查它的上下左右仍在边界内且仍是W的邻居就入队并染色。核心结构非常精简完整实现约 30 行QueueInteger queue new LinkedList(); queue.add(i * cols j); board[i][j] newColor; // 先染色再扩散 while (!queue.isEmpty()) { int pos queue.poll(); int m pos / cols, n pos % cols; // 上下左右在边界内 且 仍是旧颜色 - 入队并染色 }整个过程就像水从起点向四周逐层“漫开”这正是 BFS 逐层遍历的特征。 DFS 递归方案等价的对照写法题集给出了 BFS 版本但面试中 DFS 递归版同样常见代码更短void dfs(char[][] board, int i, int j) { if (越界 || board[i][j] ! W) return; board[i][j] O; // 进门就染色防止回头重复访问 dfs(board, i 1, j); dfs(board, i - 1, j); dfs(board, i, j 1); dfs(board, i, j - 1); }逻辑与 BFS 完全一致进入格子立即染色防回头然后沿四个方向递归扩散。 BFS vs DFS 对比怎么选对比维度BFS队列DFS递归 / 栈遍历顺序从起点逐层向外沿一条路径先钻到底空间复杂度最坏 O(min(m, n))O(m × n)受递归深度限制栈溢出风险无递归安全大图可能栈溢出代码量稍多需手写边界检查更简洁适用场景需要层数 / 最短距离信息纯连通区域标记关键结论地图较小时如题集测试用例中的 3×7 小图、19×20 大图两者性能差异可忽略选 DFS 更简洁地图很大成千上万格时DFS 递归容易栈溢出BFS 队列长度受地图短边限制更稳健若题目进一步要求“距起点的最短距离”BFS 天然支持DFS 则做不到。✅ 如何运行官方单元测试题集使用 Gradle 管理构建克隆仓库后直接运行全部测试gradle testFindingOcean.java中的测试用例包含两张地图一张 3×7 的小图验证起点所在连通域被完整标记一张 19×20 的大图其中有一条蜿蜒的水道验证水道内部的水格也能被正确染成O。相关文件路径题目描述README.md第 26 题 Finding Ocean算法实现与测试src/main/java/finding_ocean/FindingOcean.java构建脚本gradlew、gradlew.bat 面试答题小贴士边界三条件越界、遇到陆地L、遇到已标记的O三者都必须处理漏一个就是 bug强调“先染色后扩散”说明它能避免重复访问和无限递归体现工程意识主动谈 BFS 与 DFS 的复杂度取舍这是从“会写代码”到“有系统思维”的关键加分项。掌握 FindingOcean 的洪水填充模板后你其实就同时解锁了 flood fill、岛屿数量统计、迷宫寻路等一整类连通分量问题。【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考