Eisen 筆記

#994. Rotting Oranges

題目描述

給你一個m x n``grid每個格子內會有三個數值的其中一個。

  • 0表示是個空格子。
  • 1表示是個新鮮的橘子。
  • 2表示是個腐爛的橘子。

每過一分鐘，新鮮的橘子的四周如果有腐爛的橘子，新鮮的橘子會一起腐爛。

回傳所有橘子都腐爛所花費的最小時間，如果不可能全部腐爛則回傳-1。

限制條件

  1. m == grid.length
  2. n == grid[i].length
  3. 1 <= m, n <= 10
  4. grid[i][j] 只會是 0, 1, 2.

解題思路

我們會有幾件事需要做：

  1. 檢查所有格子。
  2. 腐爛橘子，計算腐爛時間。
  3. 新鮮橘子，檢查是否相鄰腐爛橘子。

按照以下步驟進行：

  1. 檢查格子。
  2. 遇到橘子，檢查橘子。
    1. 清點新鮮橘子數量，腐爛橘子數量，橘子位置。
    2. 計算腐爛時間，將處理過的橘子標記成已處理。

腐爛橘子不一定只有一個。

在某些案例中會出現一個區域內的腐爛橘子不只有一個的狀況，每一分鐘過去腐爛橘子就會同時蔓延，所以要注意計算時間的時候要同時計算蔓延程度才會得到真正的時間。

Solution

public class Solution {
    public int OrangesRotting(int[][] grid) {
        int ans = 0;        
        for(int i=0;i<grid.Length;i++){
            for(int j=0;j<grid[i].Length;j++){
                if(grid[i][j]==1 || grid[i][j]==2){
                    int result = CheckOranges(grid,i,j);
                    if(result == -1) return -1;
                    ans = Math.Max(ans,result);
                }                
            }
        }
        return ans;
    }
    public int CheckOranges(int[][] grid,int x,int y){
        // Memorize Oranges Area
        var oranges = new HashSet<(int,int)>();
        int freshOranges = 0;
        // Rotten oranges queue
        var rottenOranges = new List<Queue<(int,int)>>();
        // Counting Oranges
        var q = new Queue<(int,int)>();        
        q.Enqueue((x,y));
        while(q.Count!=0){
            (int px,int py) = q.Dequeue();
            if(oranges.Contains((px,py))) continue;
            if(grid[px][py]==1) freshOranges++;
            if(grid[px][py]==2) rottenOranges.Add(new Queue<(int,int)>(new List<(int,int)>{(px,py)}));
            if(InBound(grid,px+1,py) && grid[px+1][py]!=0 && !oranges.Contains((px+1,py))) q.Enqueue((px+1,py));
            if(InBound(grid,px-1,py) && grid[px-1][py]!=0 && !oranges.Contains((px-1,py))) q.Enqueue((px-1,py));
            if(InBound(grid,px,py+1) && grid[px][py+1]!=0 && !oranges.Contains((px,py+1))) q.Enqueue((px,py+1));
            if(InBound(grid,px,py-1) && grid[px][py-1]!=0 && !oranges.Contains((px,py-1))) q.Enqueue((px,py-1));
            oranges.Add((px,py));
        }
        return CountRottenTime(grid, freshOranges, rottenOranges, oranges);
    }
    public int CountRottenTime(int[][] grid, int freshOranges, List<Queue<(int,int)>> rottenOranges,HashSet<(int,int)> oranges){           
        int rottenTime = -1;        
        if(rottenOranges.Count==0) return -1;
        freshOranges+=rottenOranges.Count;        
        while(freshOranges!=0){
            foreach(var ro in rottenOranges){         
                int len = ro.Count;       
                for(int i=0;i<len;i++){
                    (int px,int py) = ro.Dequeue();
                    if(grid[px][py]==99) continue;
                    grid[px][py] = 99;
                    freshOranges--;
                    if(oranges.Contains((px+1,py))) ro.Enqueue((px+1,py));
                    if(oranges.Contains((px-1,py))) ro.Enqueue((px-1,py));
                    if(oranges.Contains((px,py+1))) ro.Enqueue((px,py+1));
                    if(oranges.Contains((px,py-1))) ro.Enqueue((px,py-1));
                }
            }            
            rottenTime++;
        }        
        return freshOranges!=0?-1:rottenTime;
    }    
    public bool InBound(int[][] grid,int x,int y){
        return x>=0 && x<grid.Length && y>=0 && y<grid[0].Length;
    }
}

複雜度分析：

  • 時間複雜度：檢查所有格子的時間是m * n，統計橘子的時間最差會是m * n，計算蔓延的時間最差也會是m * n，最差總時間會是3 * m * n，因此時間複雜度為O(m*n)。
  • 空間複雜度：在空間上會占用最大空間的是紀錄橘子的位置，最多會使用m * n的空間，腐爛橘子也有機會占用到m * n的空間，因此最差總空間會是2 * m * n，空間複雜度為O(m*n)。

學習重點

  • BFS
  • HashSet
  • Tuple
Last Updated:
Contributors: eisen