本文详解在dfs遍历网格求岛屿周长时，为何必须将visited.add((i, j))置于边界/水域判断之后、递归调用之前，否则会导致重复计数或漏计，从而错误计算周长。
本文详解在dfs遍历网格求岛屿周长时，为何必须将visited.add((i, j))置于边界/水域判断之后、递归调用之前，否则会导致重复计数或漏计，从而错误计算周长。
在使用深度优先搜索（DFS）计算岛屿周长时，一个看似微小的代码位置差异——即visited.add((i, j))放置在条件判断前还是后——会直接导致结果错误。根本原因在于：周长的本质是「陆地单元格与非陆地（水域或边界）的相邻边数」，而非访问节点数量。
我们以输入 [[0,1],[1,1]] 为例（对应2×2网格）：
0 1 1 1
理想岛屿形状如下（#表示陆地）：
# ##
其真实周长为 8（上边2 + 右边2 + 下边2 + 左边2，其中内部相邻边不计入）。
❌ 错误写法：visited.add() 放在最开头
def dfs(i, j):
if (i,j) in visited:
return 0
visited.add((i,j)) # ⚠️ 错误：过早标记所有入参坐标
if i = ni or j >= nj or grid[i][j] == 0:
return 1
return dfs(i-1,j) + dfs(i+1,j) + dfs(i,j-1) + dfs(i,j+1)
问题在于：当DFS从(0,1)出发，尝试访问上方(−1,1)时，该坐标虽越界（应贡献1单位周长），但尚未被visited记录；而当从(1,1)再次尝试访问(−1,1)时，它仍会被重新进入并再次返回1——因为visited只记录了有效陆地坐标，未覆盖越界/水域点。更严重的是，若某水域坐标被多次从不同方向抵达（如位置(0,0)在示例中被(0,1)左探和(1,0)上探两次访问），它将被重复计数，导致周长虚高。
但实际更隐蔽的问题是：过早标记使DFS无法区分「已探索的陆地」与「需统计的边界」。例如，(1,0)向左走到(1,-1)返回1，(0,0)向下走到(1,0)却因(1,0)已被标记而直接返回0——这反而漏掉了本应由(0,0)右侧边贡献的周长。
✅ 正确写法：仅对有效陆地坐标标记，且在边界检查之后
def dfs(i, j):
if i = ni or j >= nj or grid[i][j] == 0:
return 1 # 遇到边界或水，贡献1单位周长
if (i, j) in visited:
return 0 # 已访问过的陆地，不再贡献周长
visited.add((i, j)) # ✅ 仅对新发现的陆地单元格标记
return dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)
此时逻辑清晰分层：
- 第一层守卫：立即处理所有终止条件（越界/水域），每触发一次即累加1；
- 第二层守卫：跳过已访问陆地，避免无限递归与重复计算；
- 唯一标记点：确保每个陆地单元格仅被标记一次，且仅在其确认有效后。
? 关键洞察：visited集合在此算法中仅用于去重陆地访问，绝不应包含越界坐标或水域坐标。周长增量只来自四方向探索中「失败的一步」，而非「成功的一步」。
完整修正版代码
from typing import List
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
ni, nj = len(grid), len(grid[0])
visited = set()
def dfs(i, j):
# 终止条件：越界或遇到水 → 贡献1单位周长
if i = ni or j >= nj or grid[i][j] == 0:
return 1
# 已访问的陆地 → 不再贡献
if (i, j) in visited:
return 0
# 首次访问陆地 → 标记并递归探索四邻
visited.add((i, j))
return (
dfs(i - 1, j) +
dfs(i + 1, j) +
dfs(i, j - 1) +
dfs(i, j + 1)
)
# 找到第一个陆地启动DFS（题目保证至少一个岛屿）
for i in range(ni):
for j in range(nj):
if grid[i][j] == 1:
return dfs(i, j)
return 0
✅ 运行 Solution().islandPerimeter([[0,1],[1,1]]) 正确输出 8。
总结：DFS求周长的核心不是“遍历多少点”，而是“有多少次从陆地跨向非陆地”。visited仅服务于陆地去重，必须严格置于边界/水域判断之后、递归之前；任何提前标记都会破坏这一语义，导致计数失真。
