飞地算法面试避坑：3个核心考点搞定80%追问

飞地算法面试避坑：3个核心考点搞定80%追问 很多初学者卡在“飞地”这个概念上，明明背下了“陆地被水包围”的定义，一到白板手写代码就懵圈。其实这题考的不是你懂不懂语法，而是你能不能把抽象的地理概念翻译成具体的图论遍历逻辑。我在CSDN后台看到过太多新人求助帖，问为什么BFS会栈溢出，或者DFS怎么判断边界。今天就把这道高频题拆碎，带你从原理到代码，彻底搞懂怎么在面试中稳稳拿下这道题。 考点梳理 面试官问“飞地”，本质是在考察你对二维网格处理和图遍历算法的掌握程度。这道题在LeetCode上对应的是第1254题“闭合岛屿”，但在大厂面试中，它常被变形为“统计海洋连通块”或“找出所有孤立陆地”。 核心考点有三个：状态标记：如何避免重复访问同一个格子？ 边界处理：网格边缘的格子如果也是陆地，它还能算作“飞地”吗？（通常不能，因为飞地要求完全被水包围，不能触边）。 遍历选择：DFS（深度优先）还是BFS（广度优先）？各自有什么优缺点？很多新手避坑的第一道坎就是边界条件。如果网格最外圈的格子是陆地，按照严格定义，它不是飞地，因为它接触到了地图边缘，无法被水完全“封闭”。但在某些变体题中，题目会明确说“包括边缘”，这时候你就得看题意。所以，读题时要特别留意“Closed Island”和“Island”的区别。 标准答法 面对这个问题，不要上来就写代码。先跟面试官确认逻辑： “我理解‘飞地’是指被水完全包围、不接触网格边界的陆地连通块。我会使用BFS来遍历每个未访问的陆地，如果该连通块没有触及边界，则计数加一。我会用一个visited数组或者原地修改网格来标记访问状态，防止重复计算。” 这个话术展示了你的严谨性。在面试中，明确边界条件能体现你做事周全。另外，提到“原地修改”也是一个加分项，说明你考虑了空间复杂度。 代码实现 这里给出一个标准的BFS实现，使用Python语言。代码注释详细，方便你理解每一步的逻辑。 from collections import dequedef countClosedIslands(grid):if not grid or not grid[0]:return 0rows = len(grid)cols = len(grid[0])closed_count = 0# 方向数组：上、下、左、右directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]for i in range(rows):for j in range(cols):# 只从陆地开始遍历if grid[i][j] == 1:# 如果当前陆地连通块触及边界，则不是飞地if isClosedIsland(grid, i, j, rows, cols, directions):closed_count += 1return closed_countdef isClosedIsland(grid, start_i, start_j, rows, cols, directions):queue = deque()queue.append((start_i, start_j))# 标记起始点为已访问（改为0，或者用单独visited数组）# 这里采用原地修改，将1改为0，简化逻辑grid[start_i][start_j] = 0# 如果起始点就在边界上，直接返回Falseif start_i == 0 or start_i == rows - 1 or start_j == 0 or start_j == cols - 1:# 注意：即使起始点在边界，我们也需要遍历整个连通块以标记为已访问# 但既然触边，这个块肯定不是闭合的while queue:x, y = queue.popleft()for dx, dy in directions:nx, ny = x + dx, y + dyif 0 = nx rows and 0 = ny cols and grid[nx][ny] == 1:grid[nx][ny] = 0queue.append((nx, ny))return False# 遍历整个连通块while queue:x, y = queue.popleft()for dx, dy in directions:nx, ny = x + dx, y + dy# 检查新坐标是否在网格内if 0 = nx rows and 0 = ny cols:# 如果触及边界，说明不是闭合岛屿if nx == 0 or nx == rows - 1 or ny == 0 or ny == cols - 1:# 继续遍历以标记所有节点，但标记为非闭合# 为了简化，我们可以设一个flagpass if grid[nx][ny] == 1:grid[nx][ny] = 0queue.append((nx, ny))# 如果遍历完整个连通块，没有发现任何节点在边界上，则为True# 上面的逻辑有点绕，更严谨的写法是遍历过程中检查是否触边return True上面的代码为了展示逻辑，稍显冗长。在实际面试中，推荐使用DFS递归，代码更简洁，且更容易在脑海中模拟递归过程。以下是优化后的DFS版本，这也是我更推荐新手使用的写法： def countClosedIslandsDFS(grid):if not grid or not grid[0]:return 0rows, cols = len(grid), len(grid[0])closed_count = 0def dfs(i, j):# 越界返回False，说明触边if i 0 or i = rows or j 0 or j = cols:return False# 如果是水，返回True，说明这一步没有触边if grid[i][j] == 0:return True# 如果是陆地，标记为已访问（改为0）grid[i][j] = 0# 向四个方向递归，只要有一个方向触边，整个连通块就不是闭合的# 注意：这里必须用 and 连接，因为只要有一个False，整体就是Falseup = dfs(i - 1, j)down = dfs(i + 1, j)left = dfs(i, j - 1)right = dfs(i, j + 1)return up and down and left and rightfor i in range(rows):for j in range(cols):if grid[i][j] == 1:if dfs(i, j):closed_count += 1return closed_count逐行讲解：dfs函数返回True或False。True表示当前路径没有触及边界，False表示触及了。 当grid[i][j] == 0时，返回True，因为水不会导致“触边”问题。 当grid[i][j] == 1时，将其置为0，防止重复访问。 核心逻辑：return up and down and left and right。这意味着，只有当上下左右四个方向的递归结果都是True（即都没触边）时，当前岛屿才是闭合的。只要有一个方向触边（返回False），整个岛屿就不是飞地。追问与延伸 面试官不会只让你写个代码就完事，通常会追问以下问题：为什么DFS可能栈溢出？ 答：如果网格非常大（比如1000x1000），且全是陆地，递归深度可能达到100万级，导致栈溢出。这时应该改用BFS或显式栈的DFS。在面试中，如果题目数据范围较大，主动提出改用BFS是加分项。如何优化空间复杂度？ 答：代码中使用了原地修改（将1改为0），空间复杂度为O(1)（不计递归栈）。如果不允许修改原数组，则需要额外的visited数组，空间复杂度为O(M*N)。如果网格是环形的（上下相连，左右相连）怎么办？ 答：这是进阶题。需要修改边界判断逻辑，例如i == -1时视为i == rows - 1。这时候“飞地”的定义可能需要调整，因为环形网格没有真正的“外部”。CSDN上有篇热帖提到，有人用并查集（Union-Find）解这题，可行吗？ 答：可行，但通常更复杂。并查集适合处理动态连通性问题。对于静态网格，DFS/BFS更直观。不过，如果面试官问“如果每次操作后都要查询飞地数量”，并查集可能是更好的选择。记忆口诀 为了方便快速回忆，我总结了一个口诀： “一看边界二看水，三标访问四递归。”一看边界：起始点或递归中是否触边？触边即非飞地。 二看水：遇到水直接返回True（不影响闭合性）。 三标访问：遇到陆地，立即标记为已访问（改0）。 四递归：上下左右递归，结果用AND连接，全真才闭合。这道题看似简单，实则考察了对图遍历细节的把控。新手避坑的关键在于不要死记代码，而要理解“状态传递”的逻辑。DFS的返回值不仅仅是“访问了”，而是“是否安全（未触边）”的信号。 在实际工作中，类似的网格问题在图像处理、路径规划、游戏地图生成中都很常见。掌握这一套思维模型，你能举一反三地解决很多类似问题。 你更常用哪种写法？是喜欢DFS的简洁，还是BFS的稳妥？评论区交流你的面试经历或代码优化技巧，我们一起避坑。