前往
大廳
主題

LeetCode - 994. Rotting Oranges 解題心得

Not In My Back Yard | 2022-02-15 00:00:01 | 巴幣 0 | 人氣 153

題目連結:


題目意譯:
你被給定一個 m × n 網格 grid 其中每個格子可以有以下三種值:
0 代表著一個空格子,
1 代表著一顆新鮮的橘子,或是
2 代表著一顆腐敗的橘子。

每分鐘,任一顆位於與任一顆腐敗的橘子之四方向(上下左右)相鄰位置的新鮮橘子將會腐爛掉。

回傳最小所需經過的分鐘數使得沒有任何格子包含著新鮮的橘子。如果這個情況不可能發生,則回傳 -1。

限制:
m == grid.length
n == grid[i].length
1 ≦ m 、 n ≦ 10
grid[i][j] 只會是 0 、 1 或是 2。



範例測資:
範例 1:
輸入: grid = [[2,1,1],[1,1,0],[0,1,1]]
輸出: 4

範例 2:
輸入: grid = [[2,1,1],[0,1,1],[1,0,1]]
輸出: -1
解釋: 左下角的橘子(第 2 列,第 0 行)永遠不會腐爛,因為腐化只發生於四個方向上。

範例 3:
輸入: grid = [[0,2]]
輸出: 0
解釋: 由於第 0 分鐘已經沒有任何新鮮的橘子了,所以答案就只是 0。


解題思維:
就是單純地從那些腐爛的橘子開始按照廣度優先搜尋(Breadth First Search,BFS)的精神擴散到其他橘子上。

當無法擴散後,我們就判斷還剩多少新鮮的橘子。如果還有新鮮的橘子,則回傳 -1;反之,回傳我們現在是在第幾分鐘即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作