'Island perimeter problem - cannot count all neighbor cells

I'm working on the Island Perimeter Problem from LeetCode.

I tried to use the DFS algorithm, based on LeetCode#200, to solve this problem. For example 1, the output should be 16 but my output was 10. It seemed that not all neighbor cells were counted. Can anyone see any problems with the algorithm below?

class Solution(object):

def islandPerimeter(self, grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    # plus 4 edges for the first cell
    cnt = 4
    def dfs(grid,i,j,cnt):
        # return if the cell is out of the grid or equals to 0
        if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == 0: return 
        # put counted cell to 0 for avoiding duplicate count
        grid[i][j] = 0
        # plus 2 edges for each neighbor cell
        cnt += 2
        # search all neighbor nodes
        dfs(grid,i-1,j,cnt)
        dfs(grid,i+1,j,cnt)
        dfs(grid,i,j-1,cnt)
        dfs(grid,i,j+1,cnt)
        return cnt
    
    for i in range (len(grid)):
        for j in range (len(grid[0])):
            # find the first node equals to 1
            if grid[i][j] == 1:
               cnt += dfs(grid,i,j,cnt)
             
    return cnt
pythonalgorithmdata-structures


Solution 1:[1]

from typing import List
# perimeter means count the edges that touches the water
class Solution:
    def islandPerimeter(self,grid:List[List[int]])->int:
        ROWS,COLS=len(grid),len(grid[0])
        visited=set()
        def dfs(r,c):
            # base case we are out of bound or we reached water
            if r<0 or r==ROWS or c==COLS or c<0 or grid[r][c]==0:
                # that means we are on the border. so we return 1
                return 1
            if (r,c) in visited:
                return 0
            visited.add((r,c))
            return dfs(r+1,c)+dfs(r-1,c)+dfs(r,c+1)+dfs(r,c-1)
        # we start from land portion
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c]==1:
                    return dfs(r,c)

Solution 2:[2]

You can simplify your code to the following

def island_perimeter(grid):
    island_size = sum([i for l in grid for i in l])
    perimeter_size = island_size * 2 + 2

    # correct for inner tiles
    for i in range(len(grid) - 1):
        for j in range(len(grid[i]) - 1):
            if (grid[i][j] == 1 and grid[i+1][j] == 1 
                    and grid[i][j+1] == 1 and grid[i+1][j+1] == 1):
                perimeter_size -= 2

    return perimeter_size

Given the problem description in the link you provided, both the island and the surrounding see are connect spaces. There is only one island and there are no lakes.

You can show by induction that an island of size one has a perimeter of four. And by adding a piece of island (size 1) to the some arbitrary but fixed sized island (size n) it will extend the perimeter by 2. As a correction, whenever an island of size 2x2 is created the perimeter size needs to be decreased again by two. Hence the equation given in the function above.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Yilmaz
Solution 2

Related Questions