To solve the problem of counting the number of islands in a grid (where an island is a group of adjacent land cells connected horizontally or vertically), we can use the Breadth-First Search (BFS) algorithm. This approach efficiently explores all connected land cells and marks them as visited to avoid re-counting.

Approach

1. Iterate through each cell: For every cell in the grid, check if it is a land cell (1).
2. BFS for connected land: When a land cell is found, increment the island count and use BFS to explore all adjacent land cells. Mark these cells as visited (by setting them to 0) to prevent reprocessing.
3. Edge Cases: Handle empty grids, grids with no land, or grids with all land cells.

Solution Code

from collections import deque

def numIslands(grid):
    if not grid or not grid[0]:
        return 0

    rows = len(grid)
    cols = len(grid[0])
    island_count = 0

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':  # Adjust to 1 if grid uses integers
                island_count += 1
                # BFS to mark all connected land as visited
                queue = deque()
                queue.append((i, j))
                grid[i][j] = '0'  # Mark as visited

                while queue:
                    x, y = queue.popleft()
                    # Check all four directions (up, down, left, right)
                    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
                    for dx, dy in directions:
                        nx = x + dx
                        ny = y + dy
                        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                            queue.append((nx, ny))
                            grid[nx][ny] = '0'

    return island_count

Explanation

• BFS Exploration: For each land cell, BFS explores all adjacent cells (up, down, left, right). This ensures we cover the entire island connected to the starting cell.
• Visited Marking: By setting visited cells to 0, we avoid reprocessing the same land cell multiple times, which optimizes the algorithm.
• Efficiency: The algorithm runs in *O(rows cols) time complexity, as each cell is visited exactly once. The space complexity is O(min(rows, cols))** due to the queue (in the worst case, the queue size is the number of cells in the largest row or column).

This approach is reliable and handles all edge cases, making it an ideal solution for counting islands in a grid. Adjust the check for '1' to 1 if the grid uses integer values instead of strings.

作者声明:本文包含人工智能生成内容。