Perimeter Island

Recursively find the perimeter of an island in a 2D grid given a point on the island.

The Idea: DFS through the grid. Search through all 8 half orthogonal directions on the euclidean plane.

Complexity: O(|P|) time and space where |P| is the length of the perimeter

def perimeter_island_rec(grid, r, c):
    perimeter = [0]
    visited = set()

    def is_valid(r, c):
        return (r >= 0 and r < len(grid) and
                c >= 0 and c < len(grid[0]))

    ops = [-1, 0, 1]
    def dfs(r, c):
        visited.add((r, c))
        perimeter[0] += 1
        for r_op in ops:
            for c_op in ops:
                new_r = r + r_op
                new_c = c + c_op
                if (is_valid(new_r, new_c) and
                            grid[new_r][new_c] == 1 and
                            (new_r, new_c) not in visited and
                            not(new_r == 0 and new_c == 0)):
                    dfs(new_r, new_c)

    dfs(r, c)
    return perimeter[0]


grid = [[0,0,0,0,0,0,0,0],
        [0,1,1,1,1,1,1,0],
        [1,0,0,0,0,0,0,1],
        [1,0,0,0,0,0,0,1],
        [0,1,0,0,0,0,1,0],
        [0,1,1,1,1,1,1,0]]
print(perimeter_island_rec(grid, 1,1)) # 18