Number of Islands

Q: Какова временная сложность задачи Number of Islands?

O(rows × cols). Обход проверяет каждую клетку один раз, а каждая клетка суши один раз попадает в стек или очередь и проверяет четыре соседние клетки. Отметки посещённых клеток и стек или очередь занимают O(rows × cols) памяти на карте, полностью состоящей из суши.

Q: Следует ли использовать BFS или DFS для задачи «Количество островов»?

Оба варианта правильны с точки зрения времени и пространства, потому что достаточно пометить каждую клетку острова. BFS с очередью никогда не использует рекурсию; DFS так же безопасен, если использует явный стек.

Q: Сможешь решить задачу «Количество островов» с помощью системы непересекающихся множеств?

Да. Помести каждый участок суши в отдельное множество и начни счёт с количества участков суши. Объединяй каждую пару соседних участков суши и уменьшай счёт на единицу, когда объединение связывает два разных множества. С компрессией путей время выполнения близко к O(rows × cols).

Q: Можешь ли ты подсчитать острова без отдельного массива seen?

Да, если можно изменять карту: превращайте каждую клетку суши в воду, как только до неё доберётесь. Во многих языках нельзя изменять строки на месте, поэтому сначала скопируйте строки в сетку символов — это потребует столько же памяти, сколько и отметки о посещённых клетках.

СреднеГрафы

+10

Тебе дана карта в виде списка строк одинаковой длины, где '1' — квадрат суши, а '0' — квадрат воды. Два квадрата суши принадлежат одному острову, если они соприкасаются сторонами: сверху, снизу, слева или справа. Квадраты, соприкасающиеся только углами, не соединены. Верни количество островов.

Функция

numIslands(grid: string-array) → integer

gridstring-array: карту, по одной строке на ряд
Возвращаетinteger: количество островов

Ограничения

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Все строки имеют одинаковую длину.
Каждый символ — это '0' или '1'.

Примеры

Ввод: grid = ["11000", "11000", "00100", "00011"]
Вывод: 3
Пояснение: Четыре квадрата в левом верхнем углу образуют один остров. Средний квадрат в третьем ряду касается их только углом, поэтому это второй остров. Пара квадратов внизу справа — третий остров.

Дополнительный вопрос

Теперь суша появляется на карте воды по одной клетке за раз. Можешь сообщать количество островов после появления каждой новой клетки, не просматривая всю карту заново?

Решение

Считай каждую клетку суши узлом, соединённым с соседними клетками суши: остров — это одна связная область. Просканируй карту и каждый раз, когда встречаешь ещё не посещённую сушу, считай новый остров и выполни заливку с пометкой, отмечая каждую его клетку, чтобы при сканировании она больше не учитывалась.

Заливка с явным стеком (поиск в глубину)

Идея

Непомеченная клетка суши не может принадлежать острову, который ты уже посчитал, потому что при подсчёте острова отмечаются все его клетки. Значит, она начинает новый остров. Остальные клетки отмечает стек, которым ты управляешь сам: каждая извлечённая из стека клетка добавляет в него своих непомеченных соседей на суше, и когда стек пуст, весь остров отмечен.

Собственный стек важен, потому что рекурсивное заполнение может углубиться на 22,500 вызовов на карте 150 × 150, полностью занятой сушей. Каждая клетка добавляется в стек не более одного раза и проверяет четырёх соседей, поэтому время работы составляет O(rows × cols). Для отметок и стека требуется O(rows × cols) памяти, если вся карта занята сушей.

Алгоритм

Создай отметку посещения для каждой клетки и установи счётчик в 0.
Просканируй каждую клетку, пропуская воду и уже отмеченные клетки.
На непосещённой суше увеличь счётчик на 1, отметь клетку и помести её в стек.
Пока стек не пуст, извлекай клетку и помещай в стек каждого её соседа в пределах карты, который является непосещённой сушей, предварительно отметив его.
Когда сканирование закончится, верни счётчик.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            # Land that no island has claimed yet: a new island.
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        # Mark on push, so no square enters the stack twice.
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Заливка с использованием очереди (BFS)

Идея

Подсчёт работает так же; меняется только порядок обхода. Очередь берёт клетки из начала и добавляет непомеченных соседей суши в конец, поэтому обходит остров кольцами: сначала первую клетку, затем все клетки на расстоянии одного шага, потом — на расстоянии двух шагов. Каждая клетка по-прежнему посещается один раз, за время и с использованием памяти O(rows × cols).

Порядок обхода кольцами задаёт расстояние каждой клетки от начальной, поэтому тот же цикл позволяет находить кратчайшие пути на сетке, если хранить для каждой клетки ещё одно число.

Алгоритм

Создай отметку посещения для каждой клетки и установи счётчик на 0.
Просканируй каждую клетку, пропуская воду и уже посещённые клетки.
На ещё не посещённой суше увеличь счётчик на 1, отметь клетку и помести её в пустую очередь.
Пока в очереди есть клетки, извлеки одну из начала и добавь в конец каждого её соседа в пределах карты, если это ещё не посещённая суша; отмечай соседа при добавлении.
Верни счётчик, когда сканирование завершится.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Ловушки и крайние случаи

Отмечать клетку, когда вынимаешь её из стека или очереди, а не когда добавляешь. Тогда одна и та же клетка добавляется несколько раз.
Сравнивать клетку с числом 1 вместо символа '1'. Каждая строка — это строка, поэтому каждая клетка является символом.
Читать соседнюю клетку до проверки 0 ≤ row < rows и 0 ≤ col < cols. Тогда для клетки суши на краю чтение выйдет за пределы карты.
Реализовывать заливку рекурсивно. По умолчанию Python останавливается после 1 000 вызовов, а в других языках на одном большом острове может переполниться стек.
Извлекать первый элемент списка Python с помощью pop(0), что требует времени, пропорционального размеру списка. Используйте collections.deque и popleft().

Частые вопросы4

Какова временная сложность задачи Number of Islands?

O(rows × cols). Обход проверяет каждую клетку один раз, а каждая клетка суши один раз попадает в стек или очередь и проверяет четыре соседние клетки. Отметки посещённых клеток и стек или очередь занимают O(rows × cols) памяти на карте, полностью состоящей из суши.

Следует ли использовать BFS или DFS для задачи «Количество островов»?

Оба варианта правильны с точки зрения времени и пространства, потому что достаточно пометить каждую клетку острова. BFS с очередью никогда не использует рекурсию; DFS так же безопасен, если использует явный стек.

Сможешь решить задачу «Количество островов» с помощью системы непересекающихся множеств?

Да. Помести каждый участок суши в отдельное множество и начни счёт с количества участков суши. Объединяй каждую пару соседних участков суши и уменьшай счёт на единицу, когда объединение связывает два разных множества. С компрессией путей время выполнения близко к O(rows × cols).

Можешь ли ты подсчитать острова без отдельного массива seen?

Да, если можно изменять карту: превращайте каждую клетку суши в воду, как только до неё доберётесь. Во многих языках нельзя изменять строки на месте, поэтому сначала скопируйте строки в сетку символов — это потребует столько же памяти, сколько и отметки о посещённых клетках.

def numIslands(grid):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

grid = ["11000", "11000", "00100", "00011"]

Ожидаемый вывод