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

发布时间：2020-12-14 05:04:12 所属栏目：百科来源：网络整理

导读：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-dire

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..<C
10             {
11                 if grid[i][j] == 2
12                 {
13                     bfs(grid,&ans,i,j)
14                 }
15             }
16         }
17         var res:Int = 0
18         for i in 0..<R
19         {
20             for j in 0..<C
21             {
22                 if grid[i][j] == 1
23                 {
24                     if ans[i][j] == 0
25                     {
26                         return -1
27                     }         
28                     res = max(res,ans[i][j])
29                 }
30                 
31             }
32         }
33         return res
34     }
35     
36     func bfs(_ grid: [[Int]],_ ans: inout [[Int]],_ sx:Int,_ sy:Int)
37     {
38         var R:Int = grid.count
39         var C:Int = grid[0].count
40         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] + 1
46             for d in D
47             {
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] = cost
53                     q.append([x,y,cost])
54                 }
55             }
56         }        
57     }
58 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!