Island perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0]]

Answer: 16 Explanation: The perimeter is the 16 yellow stripes in the image below:

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        default_cell_peri = 4
        total_perimeter = 0
        #print 'rows=', rows, 'cols=', cols
        for r in xrange(rows):
            for c in xrange(cols):
                if grid[r][c] == 1:
                    cell_peri = default_cell_peri
                    #print 'r=', r, 'c=', c
                    # do inspection of e,w,n,s and decrement default_cell_peri
                    if r-1 >=0 and grid[r-1][c] == 1: # land in North
                        cell_peri -= 1
                    if r+1 <= (rows-1) and grid[r+1][c] == 1: # land in South
                        cell_peri -= 1
                    if c-1 >= 0 and grid[r][c-1] == 1: # land in West
                        cell_peri -= 1
                    if c+1 <= (cols-1) and grid[r][c+1] == 1: # land in East
                        cell_peri -= 1

                    total_perimeter += cell_peri

        return total_perimeter

Last updated

Was this helpful?