195. Зоны покрытия при включении вышек по одной

Карта района разбита на сетку h × w. После аварии МТС включает базовые станции по одной: towers[t] = [r, c] — клетка, где покрытие появилось на шаге t.

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

В работе: Штаб восстановления видит на табло, сколько «островов» связи осталось: на карте 1000 × 1000 клеток и 200 000 включений, пересчёт обходом после каждого — 10¹¹ операций.

Пример 1

h = 3
w = 3
towers = [[0, 0], [0, 2], [1, 1], [0, 1], [2, 2]]

[1, 2, 3, 1, 2]

Пример 2

h = 1
w = 1
towers = [[0, 0], [0, 0]]

[1, 1]

Ограничения

• 1 ≤ h, w ≤ 1000
• 1 ≤ длина towers ≤ 2·10⁵
• 0 ≤ r < h, 0 ≤ c < w
• Лимит — 3 с на тест (3000 мс).

def coverage_zones(h, w, towers):

Источник: наша задача на данных МТС. Условие пересказано своими словами.