Teaching Kids Programming – Recursive Depth First Search Algorithm to Count the Surrounded Islands


Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two-dimensional integer matrix matrix containing 1s and 0s. 1 represents land and 0 represents water. An island is a group of 1s that are neighboring whose perimeter is surrounded by water. Return the number of completely surrounded islands.

Constraints
n, m ≤ 250 where n and m are the number of rows and columns in matrix.
Example 1
Input

1
2
3
4
5
6
7
8
matrix = [
    [1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
matrix = [
    [1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

Output
1
Explanation
There’s 2 islands but only the middle island is completely surrounded.

Hints:
DFS traverse the islands connected to the borders. The ones left to visit are the floating islands.

Recursive Depth First Search Algorithm to Count the Surrounded Islands

We can perform Depth First Search Algorithm to mark the land (1) as water (0) starting all the land pixels on the border. And then we can perform the DFS on the inner land pixels and increment the counter along the way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def solve(self, matrix):
        if not matrix:
            return 0
        rows, cols = len(matrix), len(matrix[0])
 
        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return
            if not matrix[r][c]:
                return 
            matrix[r][c] = 0
            for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                dfs(r + dx, c + dy)
 
        for r in range(rows):
            if matrix[r][0]:
                dfs(r, 0)
            if matrix[r][cols - 1]:
                dfs(r, cols - 1)
 
        for c in range(cols):
            if matrix[0][c]:
                dfs(0, c) 
            if matrix[rows - 1][c]:
                dfs(rows - 1, c)
 
        ans = 0
        for r in range(1, rows - 1):
            for c in range(1, cols - 1):
                if matrix[r][c]:
                    dfs(r, c)
                    ans += 1                    
        return ans
class Solution:
    def solve(self, matrix):
        if not matrix:
            return 0
        rows, cols = len(matrix), len(matrix[0])

        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return
            if not matrix[r][c]:
                return 
            matrix[r][c] = 0
            for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                dfs(r + dx, c + dy)

        for r in range(rows):
            if matrix[r][0]:
                dfs(r, 0)
            if matrix[r][cols - 1]:
                dfs(r, cols - 1)

        for c in range(cols):
            if matrix[0][c]:
                dfs(0, c) 
            if matrix[rows - 1][c]:
                dfs(rows - 1, c)

        ans = 0
        for r in range(1, rows - 1):
            for c in range(1, cols - 1):
                if matrix[r][c]:
                    dfs(r, c)
                    ans += 1                    
        return ans

The time and space complexity is both O(RC) where R and C are the dimensions for rows and columns. Each pixel is visited constant number of times.

Island Problems and Algorithms:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
565 words
Last Post: The C Function to Print a Char Array (String) in Hexadecimal
Next Post: Teaching Kids Programming - Longest Zero Sublist Sum via Prefix Sum

The Permanent URL is: Teaching Kids Programming – Recursive Depth First Search Algorithm to Count the Surrounded Islands

Leave a Reply