題目

  • 題目連結
  • 目標函式 : orangesRotting(grid)
    • Input : grid: List[List[int]]
    • Output : int

解題概念

  • 題意 : 給定一 m x n 的二維陣列 grid，其中每一格會出現三種數值之一：
    • 0 : 代表空格
    • 1 : 代表新鮮橘子
    • 2 : 代表腐敗橘子
  • 而每過一分鐘，與腐敗橘子於四個方向相鄰之新鮮橘子會腐爛
  • 需要回傳必須經過的最小分鐘數，直到 grid 中沒有新鮮橘子。如果不可能，則回傳 -1

我的寫法

  • 想法 : 此題是經典的 Flood Fill Algorithm 的題目，而此題我使用 BFS
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    def orangesRotting(self, grid):
        
        cnt = 0
        n = len(grid[0])
        m = len(grid)
        queue = []

        # 找出 grid[i][j] = 2 的地方
        temp = []
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == 2:
                    grid[i][j] = 1
                    temp.append([i, j])

        DIR = [0, 1, 0, -1, 0]
        queue.append(temp)
        while len(queue) != 0:
            nodes = queue.pop(0)
            temp = []
            while len(nodes) != 0:
                node = nodes.pop(0)
                i, j = node[0], node[1]
                if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
                    continue
                grid[i][j] = 2
                
                for k in xrange(4):
                    temp.append([i + DIR[k], j + DIR[k + 1]])
            if temp != [] :
                queue.append(temp) 
                cnt += 1

        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == 1:
                    return -1
        return cnt - 1
  • 成效 :
    • Time Complexity : Wrong Answer
    • 遇到之困難 : 上述程式碼無法處理以下狀況
      1. 當 grid 中只有 0
      2. 當 grid 中只有 1

解答 or 其他優秀寫法

  • 想法 :
    1. 使用了 fresh_cnt 去紀錄新鮮橘子數量，這樣就不用特別去處理特殊案例
    2. 每次對 Queue 做 pop 時，改使用 for loop，這樣可以限制該次迴圈的次數，就不用像我一樣用多層 list 去處理
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    def orangesRotting(self, grid):
        
        fresh_cnt = 0 # 紀錄新鮮橘子之數量
        minutes_passed = 0 # 紀錄已度過之分鐘數
        n = len(grid[0])
        m = len(grid)
        queue = []

        
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == 2: # 若找到 grid[i][j] = 2
                    queue.append([i, j]) # 則將該點加到 Queue 中
                elif grid[i][j] == 1: # 若找到 grid[i][j] = 1
                    fresh_cnt += 1 # 紀錄比數 + 1 

        DIR = [0, 1, 0, -1, 0]
        while len(queue) != 0  and fresh_cnt > 0:

            # 分鐘數 + 1
            minutes_passed += 1
            
            # 取出當前 Queue 中所有的元素
            for _ in range(len(queue)):
                node = queue.pop(0)

                # 往四個方向查看
                for k in xrange(4):
                    i = node[0] + DIR[k]
                    j = node[1] + DIR[k + 1]
                
                    if i < 0 or i >= m or j < 0 or j >= n:
                        continue

                    if grid[i][j] != 1:
                        continue

                    # 若發現 grid[i][j] == 1
                    fresh_cnt -= 1 # 新鮮橘子數 -1
                    grid[i][j] = 2 # 更改該格數值

                    queue.append([i, j]) # 加入下一回合之 Queue 中

        return minutes_passed if fresh_cnt == 0 else -1 # 若 fresh_cnt為零，代表全部皆腐爛
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 29 ms (faster than 73.48%)
    • Memory Usage: 13.32 MB (more than 29.84%)