Задача: 827. Making A Large Island
Сложность: hard

Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.

Верните размер самого большого острова в grid после выполнения этой операции.

Остров — это группа 1, соединенных в 4 направлениях.

Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

👨‍💻 Алгоритм:

1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.

2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1.

3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.

😎 Решение:

class Solution {
    private val directions = arrayOf(
        intArrayOf(-1, 0), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(0, 1)
    )
    private lateinit var grid: Array<IntArray>
    private var N = 0

    fun largestIsland(grid: Array<IntArray>): Int {
        this.grid = grid
        N = grid.size

        var index = 2
        val area = IntArray(N * N + 2)
        for (r in 0 until N) {
            for (c in 0 until N) {
                if (grid[r][c] == 1) {
                    area[index] = dfs(r, c, index)
                    index++
                }
            }
        }

        var ans = area.maxOrNull() ?: 0
        for (r in 0 until N) {
            for (c in 0 until N) {
                if (grid[r][c] == 0) {
                    val seen = mutableSetOf<Int>()
                    for ((nr, nc) in neighbors(r, c)) {
                        if (grid[nr][nc] > 1) {
                            seen.add(grid[nr][nc])
                        }
                    }
                    ans = maxOf(ans, 1 + seen.sumOf { area[it] })
                }
            }
        }
        return ans
    }

    private fun dfs(r: Int, c: Int, index: Int): Int {
        var ans = 1
        grid[r][c] = index
        for ((nr, nc) in neighbors(r, c)) {
            if (grid[nr][nc] == 1) {
                grid[nr][nc] = index
                ans += dfs(nr, nc, index)
            }
        }
        return ans
    }

    private fun neighbors(r: Int, c: Int): List<Pair<Int, Int>> {
        val result = mutableListOf<Pair<Int, Int>>()
        for (dir in directions) {
            val nr = r + dir[0]
            val nc = c + dir[1]
            if (nr in 0 until N && nc in 0 until N) {
                result.add(nr to nc)
            }
        }
        return result
    }

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