0463. Island Perimeter

0463. Island Perimeter#

Problem#

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 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”, meaning the water inside 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.

Examples#

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.Input: image

Example 2:

Input: grid = [[1]]
Output: 4

Example 3:

Input: grid = [[1,0]]
Output: 4

Constraints:#

m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], color < 216
0 <= sr < m
0 <= sc < n

Analysis#

  • how to calculate perimeter? -> each land cell will contribute 4 - len(adj) to the whole perimeter, where the adj is the adjacent land cells of current land cell.

  • How to get all land cells as one island?

  • Flow:

    • repeatly do:

      • traverse each land cell

      • calculate the number of its adjacent land cells

    • get total perimeter = 4 * number of land cells - the total number of the adjacenet land cells for each land cell

  • Assumptions:

    • Only one island: as long as we find the first land cell, we can run BFS or DFS to traverse all the land cells

    • No lake

Solution#

"""A solution using DFS"""
def solution(grid):

    m, n = len(grid), len(grid[0])

    # get the first land cell
    first = []
    r = 0
    while r < m:
        c = 0
        # move column wise
        while c < n:
            if grid[r][c] == 0:
                c += 1
            else:
                first = (r, c)
                break
        r += 1
    # 
    if len(first) < 1:
        return 0

    # traverse from the first detected land cell
    # dfs
    label = 2

    def dfs(grid, sr, sc, num_lands, num_adjs):
        
        # if connected:
        if grid[sr][sc] == 1:
            grid[sr][sc] = label
            num_lands += 1
            num_adjs += get_num_adjs(grid, sr, sc)

            # dfs
            if sr > 0:
                num_lands, num_adjs = dfs(grid, sr - 1, sc, num_lands, num_adjs)
            if sr < m - 1:
                num_lands, num_adjs = dfs(grid, sr + 1, sc, num_lands, num_adjs)
            if sc > 0:
                num_lands, num_adjs = dfs(grid, sr, sc - 1, num_lands, num_adjs)
            if sc < n - 1:
                num_lands, num_adjs = dfs(grid, sr, sc + 1, num_lands, num_adjs)

        return num_lands, num_adjs

    def get_num_adjs(grid, sr, sc):
        # up
        adjs = []
        num_adjs = 0
        if sr > 0:
            adjs.append((sr-1, sc))
        if sr < m - 1:
            adjs.append((sr+1, sc))
        if sc > 0:
            adjs.append((sr, sc-1))
        if sc < n - 1:
            adjs.append((sr, sc+1))

        for r, c in adjs:
            if grid[r][c] == 1 or grid[r][c] == 2:
                num_adjs += 1

        return num_adjs

    num_lands, num_adjs = dfs(grid, first[0], first[1], 0, 0)
    print(num_lands, num_adjs)
    perim = 4*num_lands - num_adjs

    return perim


# tests
grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
print(solution(grid))

grid = [[1]]
print(solution(grid))

grid = [[1,0]]
print(solution(grid))

7 12
16
1 0
4
1 0
4
Contents