Задача: 994. Rotting Oranges
Сложность: medium

Дан m x n сетка, где каждая ячейка может иметь одно из трех значений:

0, представляющее пустую ячейку,
1, представляющее свежий апельсин,
2, представляющее гнилой апельсин.
Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым.

Верните минимальное количество минут, которые должны пройти, пока в ячейке не останется свежих апельсинов. Если это невозможно, верните -1.

Пример:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

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

1⃣Инициализация очереди и подсчет апельсинов:
Пройдите по всей сетке, добавьте все гнилые апельсины в очередь и подсчитайте общее количество свежих апельсинов.
Если нет свежих апельсинов, верните 0.

2⃣Использование BFS для распространения гнили:
Выполняйте BFS, начиная с всех гнилых апельсинов, добавленных в очередь.
Каждый раз, когда апельсин становится гнилым, уменьшайте счетчик свежих апельсинов.
Если свежих апельсинов больше не осталось, верните текущее количество минут.

3⃣Проверка оставшихся свежих апельсинов:
Если после завершения BFS все еще остаются свежие апельсины, верните -1.

😎 Решение:

class Solution {
    fun orangesRotting(grid: Array<IntArray>): Int {
        val queue = ArrayDeque<Pair<Int, Int>>()
        var freshCount = 0
        val directions = arrayOf(Pair(0, 1), Pair(1, 0), Pair(0, -1), Pair(-1, 0))
        
        for (i in grid.indices) {
            for (j in grid[0].indices) {
                when (grid[i][j]) {
                    2 -> queue.add(Pair(i, j))
                    1 -> freshCount++
                }
            }
        }
        
        if (freshCount == 0) return 0
        
        var minutes = 0
        while (queue.isNotEmpty()) {
            repeat(queue.size) {
                val (i, j) = queue.removeFirst()
                for ((di, dj) in directions) {
                    val ni = i + di
                    val nj = j + dj
                    if (ni in grid.indices && nj in grid[0].indices && grid[ni][nj] == 1) {
                        grid[ni][nj] = 2
                        freshCount--
                        queue.add(Pair(ni, nj))
                    }
                }
            }
            if (queue.isNotEmpty()) {
                minutes++
            }
        }
        
        return if (freshCount == 0) minutes else -1
    }
}

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