更多精彩內(nèi)容，請(qǐng)關(guān)注【力扣簡(jiǎn)單題】。

題目

難度：★★★☆☆
類(lèi)型：幾何，二維數(shù)組

題目

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

值 0 代表空單元格；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子。
每分鐘，任何與腐爛的橘子（在 4 個(gè)正方向上）相鄰的新鮮橘子都會(huì)腐爛。

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

示例

示例1

腐爛的橘子

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

示例 2

輸入：[[2,1,1],[0,1,1],[1,0,1]]
輸出：-1
解釋?zhuān)鹤笙陆堑拈僮樱ǖ?2 行， 第 0 列）永遠(yuǎn)不會(huì)腐爛，因?yàn)楦癄€只會(huì)發(fā)生在 4 個(gè)正向上。

示例 3

輸入：[[0,2]]
輸出：0
解釋?zhuān)阂驗(yàn)?0 分鐘時(shí)已經(jīng)沒(méi)有新鮮橘子了，所以答案就是 0 。

提示

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] 僅為 0、1 或 2

解答

參考官方解答。使用寬度有限搜索。

每一輪，腐爛將會(huì)從每一個(gè)爛橘子蔓延到與其相鄰的新鮮橘子上。一開(kāi)始，腐爛的橘子的深度為 0，每一輪腐爛會(huì)從腐爛橘子傳染到之相鄰新鮮橘子上，并且設(shè)置這些新的腐爛橘子的深度為自己深度 +1，我們想知道完成這個(gè)過(guò)程之后的最大深度值是多少。

因?yàn)槲覀兛偸沁x擇去使用深度值最小的（且之前未使用過(guò)的）腐爛橘子去腐化新鮮橘子，如此保證每一個(gè)橘子腐爛時(shí)的深度標(biāo)號(hào)也是最小的。

我們還應(yīng)該檢查最終狀態(tài)下，是否還有新鮮橘子。

import collections


class Solution(object):
    def orangesRotting(self, grid):
        R, C = len(grid), len(grid[0])
        A = grid

        # 把所有腐爛的橘子加入到雙向隊(duì)列中
        queue = collections.deque()
        for r, row in enumerate(A):
            for c, val in enumerate(row):
                if val == 2:
                    queue.append((r, c, 0))
        
        # 東南西北生成器
        def surrounding(r, c):
            for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
                if 0 <= nr < R and 0 <= nc < C:
                    yield nr, nc
        
        # 寬度優(yōu)先搜索
        d = 0
        while queue:
            r, c, d = queue.popleft()
            for nr, nc in surrounding(r, c):
                if A[nr][nc] == 1:
                    A[nr][nc] = 2
                    queue.append((nr, nc, d+1))
        
        # 如果還有沒(méi)有腐爛的橘子，返回-1
        if any(1 in row for row in A):
            return -1
        
        # 返回最大深度
        return d

如有疑問(wèn)或建議，歡迎評(píng)論區(qū)留言~