Задача: 305. Number of Islands II
Сложность: 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(size: Int) {
    private val parent = IntArray(size) { -1 }
    private val rank = IntArray(size)
    var count = 0
    fun addLand(x: Int) { if (parent[x] < 0) { parent[x] = x; count++ } }
    fun isLand(x: Int) = parent[x] >= 0
    fun numberOfIslands() = count
    fun find(x: Int): Int { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x] }
    fun unionSet(x: Int, y: Int) { val xset = find(x); val yset = find(y)
        if (xset == yset) return; if (rank[xset] < rank[yset]) parent[xset] = yset
        else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++ }; count-- }
}

class Solution {
    fun numIslands2(m: Int, n: Int, positions: Array<IntArray>): List<Int> {
        val dsu = UnionFind(m * n), dirs = listOf(-1, 1, 0, 0), dirc = listOf(0, 0, -1, 1)
        val answer = mutableListOf<Int>()
        for (pos in positions) {
            val land = pos[0] * n + pos[1]
            dsu.addLand(land)
            for (i in 0..3) {
                val x = pos[0] + dirs[i], y = pos[1] + dirc[i], neighbor = x * n + y
                if (x in 0 until m && y in 0 until n && dsu.isLand(neighbor)) { dsu.unionSet(land, neighbor) }
            }
            answer.add(dsu.numberOfIslands())
        }
        return answer
    }
}

Ставь 👍 и забирай 📚 Базу знаний