Leetcode 994. Rotting Oranges

1. Description

2. Solution

**解析：**Version 1，先統計新鮮水果數量，如果不存在，則時間為

，同時記錄腐敗水果的位置。按照廣度優先搜尋，記錄下一輪腐敗水果的位置，同時時間加

1

，新鮮水果數量減

1

，遞歸執行，直至不存在腐敗的水果位置或者新鮮水果為

。如果此時仍存在新鮮水果，則傳回

-1

，否則，傳回時間。

• Version 1

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        fresh = 0
        rotten = []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    rotten.append([i, j])
                elif grid[i][j] == 1:
                    fresh += 1
        if fresh == 0:
            return 0
        time = 0
        while rotten and fresh:
            temp = []
            for x, y in rotten:
                if x > 0 and grid[x-1][y] == 1:
                    grid[x-1][y] = 2
                    temp.append([x-1, y])
                    fresh -= 1
                if y > 0 and grid[x][y-1] == 1:
                    grid[x][y-1] = 2
                    temp.append([x, y-1])
                    fresh -= 1
                if x < m - 1 and grid[x+1][y] == 1:
                    grid[x+1][y] = 2
                    temp.append([x+1, y])
                    fresh -= 1
                if y < n - 1 and grid[x][y+1] == 1:
                    grid[x][y+1] = 2
                    temp.append([x, y+1])
                    fresh -= 1
            time += 1
            rotten = temp
        if fresh == 0:
            return time
        else:
            return -1           

複制

Reference

1. https://leetcode.com/problems/rotting-oranges/