腐爛的橘子

在給定的 m x n 網(wǎng)格 grid 中，每個單元格可以有以下三個值之一：

• 值 0 代表空單元格；
• 值 1 代表新鮮橘子；
• 值 2 代表腐爛的橘子。
  每分鐘，腐爛的橘子 周圍 4 個方向上相鄰 的新鮮橘子都會腐爛。

返回 直到單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)。如果不可能，返回 -1 。

示例1:

輸入：grid = [[2,1,1],[1,1,0],[0,1,1]]
輸出： 4

解題思路

使用廣度優(yōu)先搜索（BFS）算法來模擬腐爛的橘子的傳播過程。
PS: 廣度優(yōu)先搜索（BFS）算法一般使用
Queue queue = new LinkedList<>();
搭配 while(!queue.isEmpty())來實現(xiàn)
因為隊列的先進先出（FIFO）特性恰好符合 BFS 的搜索順序。

• 1、遍歷整個網(wǎng)格，將腐爛的橘子的坐標(biāo)加入隊列，并統(tǒng)計新鮮橘子的數(shù)量。
• 2、在隊列不為空的情況下，從隊列中取出腐爛的橘子，將其周圍未腐爛的橘子腐爛，并將其坐標(biāo)加入隊列。
• 3、每次從隊列中取出橘子時，時間變量加一。
• 4、在每次遍歷完整個隊列時，檢查是否還有新鮮橘子沒有被腐爛。
• 如果有，則返回 -1。
• 如果沒有，則返回時間變量減一，因為最后一個橘子腐爛不需要再等待一分鐘。

Java實現(xiàn)

public class RottingOranges {
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int freshOranges = 0; // 記錄新鮮橘子的數(shù)量
        Queue<int[]> queue = new LinkedList<>(); // 用于存儲腐爛的橘子的位置

        // 統(tǒng)計新鮮橘子的數(shù)量，并將腐爛的橘子加入隊列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    freshOranges++;
                } else if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        int minutes = 0; // 記錄經(jīng)過的分鐘數(shù)
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四個方向

        // 開始進行 BFS，直到隊列為空或者沒有新鮮橘子為止
        while (!queue.isEmpty() && freshOranges > 0) {
            int size = queue.size();
            //當(dāng)前腐爛的桔子
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                //計算上下左右腐爛的桔子
                for (int[] dir : directions) {
                    int newX = curr[0] + dir[0];
                    int newY = curr[1] + dir[1];
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1) {
                        grid[newX][newY] = 2; // 標(biāo)記為腐爛的橘子
                        queue.offer(new int[]{newX, newY});
                        freshOranges--; // 每腐爛一個橘子，新鮮橘子數(shù)量減一
                    }
                }
            }
            minutes++; // 經(jīng)過一分鐘
        }

        return freshOranges == 0 ? minutes : -1;
    }

    public static void main(String[] args) {
        RottingOranges oranges = new RottingOranges();
        int[][] grid = {
            {2, 1, 1},
            {1, 1, 0},
            {0, 1, 2}
        };
        System.out.println("Minimum minutes required: " + oranges.orangesRotting(grid));
    }
}

時間空間復(fù)雜度

• 時間復(fù)雜度：O(m * n)，其中 m 和 n 分別是網(wǎng)格的行數(shù)和列數(shù)，因為需要遍歷整個網(wǎng)格。

• 空間復(fù)雜度：O(m * n)，在最壞的情況下，隊列的大小可能會達到網(wǎng)格中所有新鮮橘子的數(shù)量，因此空間復(fù)雜度是 O(m * n)。文章來源地址http://www.zghlxwxcb.cn/news/detail-852663.html

到了這里，關(guān)于【圖論】Leetcode 994. 腐爛的橘子【中等】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！