Сложность: hard
Дан пустой двумерный бинарный массив
grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив
positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.Верните массив целых чисел
answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.
Пример:
Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]
👨💻 Алгоритм:
1⃣Инициализация:
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.
2⃣Обработка позиций:
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.
3⃣Определение количества островов:
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.
😎 Решение
class UnionFind:
def __init__(self, size): self.parent = [-1] * size; self.rank = [0] * size; self.count = 0
def addLand(self, x): if self.parent[x] < 0: self.parent[x] = x; self.count += 1
def isLand(self, x): return self.parent[x] >= 0
def numberOfIslands(self): return self.count
def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]); return self.parent[x]
def unionSet(self, x, y): xset, yset = self.find(x), self.find(y); if xset == yset: return
if self.rank[xset] < self.rank[yset]: self.parent[xset] = yset
else: self.parent[yset] = xset; if self.rank[xset] == self.rank[yset]: self.rank[xset] += 1
self.count -= 1
class Solution:
def numIslands2(self, m, n, positions):
dsu, answer, dirs, dirc = UnionFind(m * n), [], [-1, 1, 0, 0], [0, 0, -1, 1]
for pos in positions:
land = pos[0] * n + pos[1]
dsu.addLand(land)
for i in range(4):
x, y = pos[0] + dirs[i], pos[1] + dirc[i]
neighbor = x * n + y
if 0 <= x < m and 0 <= y < n and dsu.isLand(neighbor):
dsu.unionSet(land, neighbor)
answer.append(dsu.numberOfIslands())
return answer
Ставь 👍 и забирай 📚 Базу знаний