[Swift Weekly Contest 124]LeetCode994. 腐烂的橘子 | Rotting Oranges

概述In a given grid, each cell can have one of three values: the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing a rotten orange. Every minute, any fr

In a given grID,each cell can have one of three values:

the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing a rotten orange.

Every minute,any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible,return -1 instead. 

Example 1:

input: [[2,1,1],[1,0],[0,1]]Output: 4 

Example 2:

input: [[2,1]]Output: -1 Explanation: The orange in the bottom left corner (row 2,column 0) is never rotten,because rotting only happens 4-directionally. 

Example 3:

input: [[0,2]]Output: 0 Explanation: Since there are already no fresh oranges at minute 0,the answer is just 0. 

Note:

1 <= grID.length <= 10 1 <= grID[0].length <= 10 grID[i][j] is only 0, 1,or 2.

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。 

示例 1：

输入：[[2,1]]输出：4

示例 2：

输入：[[2,1]]输出：-1解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

示例 3：

输入：[[0,2]]输出：0解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。 

提示：

1 <= grID.length <= 10 1 <= grID[0].length <= 10 grID[i][j] 仅为 0、1 或 2 Runtime: 40 ms Memory Usage: 19.5 MB

 1 class Solution { 2     var D:[[Int]] = [[-1,0],[1,[0,-1],1]] 3     func orangesRotting(_ grID: [[Int]]) -> Int { 4         var R:Int = grID.count 5         var C:Int = grID[0].count 6         var ans:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:C),count:R) 7         for i in 0..<R 8         { 9             for j in 0..<C10             {11                 if grID[i][j] == 212                 {13                     bfs(grID,&ans,i,j)14                 }15             }16         }17         var res:Int = 018         for i in 0..<R19         {20             for j in 0..<C21             {22                 if grID[i][j] == 123                 {24                     if ans[i][j] == 025                     {26                         return -127                     }         28                     res = max(res,ans[i][j])29                 }30                 31             }32         }33         return res34     }35     36     func bfs(_ grID: [[Int]],_ ans: inout [[Int]],_ sx:Int,_ sy:Int)37     {38         var R:Int = grID.count39         var C:Int = grID[0].count40         var q:[[Int]] = [[Int]]()41         q.append([sx,sy,0])42         while(!q.isEmpty)43         {44             var cur:[Int] = q.removeFirst()45             var cost:Int = cur[2] + 146             for d in D47             {48                 var x:Int = cur[0] + d[0]49                 var y:Int = cur[1] + d[1]50                 if x >= 0 && y >= 0 && x < R && y < C && grID[x][y] == 1 && (ans[x][y] == 0 || ans[x][y] > cost)51                 {52                     ans[x][y] = cost53                     q.append([x,y,cost])54                 }55             }56         }        57     }58 }

总结

以上是内存溢出为你收集整理的[Swift Weekly Contest 124]LeetCode994. 腐烂的橘子 | Rotting Oranges全部内容，希望文章能够帮你解决[Swift Weekly Contest 124]LeetCode994. 腐烂的橘子 | Rotting Oranges所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。