Given a boolean matrix, find the number of islands. An island is a group of connected 1s or a standalone 1. A cell can be connected to 8 neighbors (2 vertical, 2 horizontal, and 4 diagonal).

For example, consider the following boolean matrix:

[[1, 1, 0, 0, 0],
 [1, 1, 0, 0, 0],
 [0, 0, 1, 0, 0],
 [0, 0, 0, 1, 1]]

In this matrix, there are three islands. The first island consists of the 1s in the top-left corner. The second island is the single 1 in the middle of the matrix. The third island is formed by the two 1s in the bottom-right corner.

As another example:

[[1, 0, 1, 0],
 [0, 1, 0, 1],
 [1, 0, 1, 0],
 [0, 1, 0, 1]]

This matrix contains eight islands.

Your task is to implement a function that takes a two-dimensional boolean matrix as input and returns the number of islands present in the matrix. The function should handle cases where the matrix is empty or contains no islands (all 0s). Consider edge cases where an island touches the boundary of the matrix. Can you provide an efficient algorithm to solve this problem, taking into account the 8-directional connectivity?

Number of Islands

Problem Description

Given a two-dimensional boolean matrix, find the number of islands. An island is a group of connected 1s (land) or a standalone 1. A cell in the matrix can be connected to up to 8 neighbors: 2 vertical, 2 horizontal, and 4 diagonal.

Example

Consider the following boolean matrix:

[[1, 1, 0, 0, 0],
 [1, 1, 0, 0, 0],
 [0, 0, 1, 0, 0],
 [0, 0, 0, 1, 1]]

In this matrix, there are three islands.

Naive Solution (Depth-First Search)

A brute-force approach would involve iterating through each cell of the matrix. When a '1' is encountered, we perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all connected '1's, marking them as visited to avoid recounting them as separate islands. This is inefficient since it does not consider the 8-directional connectivity.

Optimal Solution (Depth-First Search with 8-Directional Connectivity)

This solution uses Depth-First Search (DFS) to traverse the matrix and identify islands. When a '1' (land) is found, DFS is used to explore all adjacent '1's, marking them as visited. The key is to consider the 8-directional connectivity.

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    num_islands = 0

    def dfs(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0':
            return

        grid[row][col] = '0'  # Mark as visited

        # Explore 8 neighbors
        dfs(row - 1, col)      # Up
        dfs(row + 1, col)      # Down
        dfs(row, col - 1)      # Left
        dfs(row, col + 1)      # Right
        dfs(row - 1, col - 1)  # Top-Left
        dfs(row - 1, col + 1)  # Top-Right
        dfs(row + 1, col - 1)  # Bottom-Left
        dfs(row + 1, col + 1)  # Bottom-Right

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                num_islands += 1
                dfs(i, j)

    return num_islands

# Example usage:
grid1 = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]

grid2 = [
    ["1", "0", "1", "0"],
    ["0", "1", "0", "1"],
    ["1", "0", "1", "0"],
    ["0", "1", "0", "1"]
]

print(f"Number of islands in grid1: {num_islands(grid1)}") # Output: 3
print(f"Number of islands in grid2: {num_islands(grid2)}") # Output: 8

Big(O) Run-time Analysis

The time complexity is O(R * C), where R is the number of rows and C is the number of columns in the grid. This is because, in the worst case, we might visit every cell in the grid.

• The outer loops iterate through each cell of the grid (R * C).
• The dfs function, in the worst-case scenario (when the entire grid is '1'), visits each cell once.

Big(O) Space Usage Analysis

The space complexity is O(R * C) in the worst-case scenario due to the call stack of the DFS. This happens when the entire grid is filled with '1's, and the recursion depth can go up to R * C.

Edge Cases and Handling

1. Empty Grid: If the input grid is empty (i.e., None or has zero rows or columns), the function returns 0 immediately.
2. Grid with No Islands (All Zeros): The algorithm correctly identifies that there are no islands if the entire grid is filled with '0's.
3. Islands Touching the Boundary: The DFS correctly handles islands that touch the boundary of the matrix, as the boundary checks in the dfs function prevent it from going out of bounds.
4. Invalid Input: The code assumes that the grid contains only '0' and '1' characters. Error handling could be added to validate the input if necessary.

Alternative Solution (Breadth-First Search)

Instead of DFS, Breadth-First Search (BFS) could be used to explore the connected components. The approach is very similar. Instead of recursion, a queue is used to keep track of the cells to be visited. The run-time and space complexity would be similar.