LeetCode岛屿周长问题：遍历邻居时计数不全的原因排查

Hey there! Let's work through your Island Perimeter problem snag together. First, let's recap the problem to make sure we're on the same page:

Problem Context: We're solving the LeetCode Island Perimeter problem, where the sample input is [[0,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0]] and the correct perimeter is 16 (matching the 16 yellow border edges shown in the problem's reference image).

You mentioned your current approach is to find one island cell and traverse its adjacent cells, but you're sometimes missing counts of neighbors. You suspect two culprits: removing cells when visiting them, and using a recursive approach. Let's break down why these might be causing issues, plus fix them up.

Why Your Current Approach Might Be Falling Short #

1. Removing Cells When Visiting Them #

When you delete a cell (like setting it to 0) after visiting it, you're altering the grid in a way that breaks the perimeter calculation for adjacent cells. Here's why: every island cell starts with a potential 4 edges contributing to the perimeter. For every adjacent island cell, we subtract 1 (since that edge is shared, not exposed). If you delete a cell before its neighbors check it, those neighbors won't account for that shared edge—leading you to overcount their perimeter by 1 each time. For example, if cell A (1) is next to cell B (1), deleting A first means when you check B, you'll never know they shared an edge, so you'll add 4 for B instead of 3.

2. Recursive Approach Pitfalls #

Recursion itself isn't the enemy here, but missteps in how you implement it can lead to missed counts. Common issues include:

• Not checking all four directions (up, down, left, right) for every cell, which means you skip adjacent island cells.
• Relying on grid modification (deleting cells) instead of a separate visited matrix to track which cells you've already processed—this ties back to the first problem.
• Failing to handle edge cases (like cells on the grid border, where those edges are automatically part of the perimeter).

Fixed Approach Suggestions #

Option 1: Tweak Your Traversal (No More Deleting Cells) #

Instead of modifying the original grid, use a separate visited matrix (same size as your input grid) to keep track of which cells you've already checked. Here's a rough outline of how to adjust your recursive DFS:

1. Scan the grid to find the first 1 (your starting island cell).
2. Start your recursive DFS from that cell:
   • For the current cell, add 4 to the perimeter (all four edges as a starting point).
   • Check each of the four adjacent cells:
     • If an adjacent cell is an island (1) and hasn't been visited, subtract 1 from the perimeter (since it's a shared edge) and recursively visit that cell.
     • If the adjacent cell is already visited, also subtract 1 (we know it's part of the island, so that edge is shared).
   • Mark the current cell as visited so you don't process it again.

Option 2: Simplify with a Direct Count (No Traversal Needed!) #

If you want to avoid recursion or traversal altogether, there's a much simpler way. Just iterate through every cell in the grid and calculate the perimeter directly:

• For each cell that's 1, add 4 to the perimeter (all four edges).
• Then, check if the cell to the right is also 1—if yes, subtract 2 (since both cells share an edge, each loses 1 from their total perimeter).
• Do the same for the cell below the current one—if it's 1, subtract 2.

This works because every shared edge between two island cells reduces the total perimeter by 2 (each cell would have counted that edge as exposed, so we need to subtract 1 from each).

Here's a Python code snippet for this method:

def islandPerimeter(grid):
    perimeter = 0
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                perimeter += 4
                # Check right neighbor
                if j + 1 < cols and grid[i][j+1] == 1:
                    perimeter -= 2
                # Check bottom neighbor
                if i + 1 < rows and grid[i+1][j] == 1:
                    perimeter -= 2
    return perimeter

Testing this with your sample input gives exactly 16, which is the correct answer.

Key Takeaways #

• Skip modifying the original grid when traversing—use a visited matrix instead to track processed cells.
• Recursion can work, but make sure you check all four directions and handle edge cases properly.
• The direct counting method is often simpler, faster, and less error-prone for this specific problem.

内容的提问来源于stack exchange，提问作者Jay Shri