Задача: 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 {
    func orangesRotting(_ grid: [[Int]]) -> Int {
        var grid = grid
        var queue: [(Int, Int)] = []
        var freshCount = 0
        let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        var minutes = 0
        
        for i in 0..<grid.count {
            for j in 0..<grid[0].count {
                if grid[i][j] == 2 {
                    queue.append((i, j))
                } else if grid[i][j] == 1 {
                    freshCount += 1
                }
            }
        }
        
        if freshCount == 0 { return 0 }
        
        while !queue.isEmpty {
            var nextQueue: [(Int, Int)] = []
            for (i, j) in queue {
                for dir in directions {
                    let ni = i + dir.0, nj = j + dir.1
                    if ni >= 0, ni < grid.count, nj >= 0, nj < grid[0].count, grid[ni][nj] == 1 {
                        grid[ni][nj] = 2
                        freshCount -= 1
                        nextQueue.append((ni, nj))
                    }
                }
            }
            if !nextQueue.isEmpty {
                minutes += 1
            }
            queue = nextQueue
        }
        
        return freshCount == 0 ? minutes : -1
    }
}

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