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
