> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/recursion-and-dynamic-programming/perimeter-island.md).

# 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.![](https://176165416-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphwLiMOHOYPmtrx%2F-LoJHq55n17qGKUSaNW0%2F-LoJIgJXV_KEMpDsJV5t%2Fdfs_perim_grid.png?generation=1568003845229992\&alt=media)

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

```python
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
```