Решить задачу Number of Islands (LeetCode 200)?

LeetCode 200. Посчитать острова в grid (1 — land, 0 — water). Остров — connected 1s (4-directional). DFS с пометкой in-place. O(rows × cols) время.

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or grid[r][c] != '1'):
            return
        grid[r][c] = '0'   # mark visited
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

Каждый раз, как находим непосещённую '1' — новый остров, DFS помечает весь остров '0'. Альтернативы: BFS с queue (O(min(m,n)) memory worst case), Union-Find (через flatten index r*cols + c). Связанные: Max Area of Island (695), Surrounded Regions (130), Word Search (79). Паттерн — flood fill.