[Swift]LeetCode675.为高尔夫比赛砍树|CutOffTreesforGolfEvent

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10497918.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:

0 represents the obstacle can't be reached.
1 represents the ground can be walked through.
The place with number bigger than 1represents a tree can be walked through, and this positive number represents the tree's height.

You are asked to cut off all the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can't cut off all the trees, output -1 in that situation.

You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.

Example 1:

Input: 
[
 [1,2,3],
 [0,0,4],
 [7,6,5]
]
Output: 6

Example 2:

Input: 
[
 [1,2,3],
 [0,0,0],
 [7,6,5]
]
Output: -1

Example 3:

Input: 
[
 [2,3,4],
 [0,0,5],
 [8,7,6]
]
Output: 6
Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.

Hint: size of the given matrix will not exceed 50x50.

你被请来给一个要举办高尔夫比赛的树林砍树. 树林由一个非负的二维数组表示，在这个数组中：

0 表示障碍，无法触碰到.
1 表示可以行走的地面.
比1大的数 表示一颗允许走过的树的高度.

你被要求按照树的高度从低向高砍掉所有的树，每砍过一颗树，树的高度变为1。

你将从（0，0）点开始工作，你应该返回你砍完所有树需要走的最小步数。如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且至少有一颗树需要你砍。

示例 1:

输入: 
[
 [1,2,3],
 [0,0,4],
 [7,6,5]
]
输出: 6

示例 2:

输入: 
[
 [1,2,3],
 [0,0,0],
 [7,6,5]
]
输出: -1

示例 3:

输入: 
[
 [2,3,4],
 [0,0,5],
 [8,7,6]
]
输出: 6

解释: (0,0) 位置的树，你可以直接砍去，不用算步数

提示: 矩阵大小不会超过 50x50 。

Runtime: 7864 ms

Memory Usage: 19.6 MB

 1 class Solution {
 2     var dirs:[[Int]] = [[0,1],[0, -1],[1, 0],[-1, 0]]
 3     func cutOffTree(_ forest: [[Int]]) -> Int {
 4         var forest = forest
 5         //forest.sort(by:{return $0[2] < $1[2]})
 6         var pq:[[Int]] = [[Int]]()
 7         for r in 0..<forest.count
 8         {
 9             for c in 0..<forest[0].count
10             {
11                 var height:Int = forest[r][c]
12                 if height > 0
13                 {
14                     pq.append([r, c, height])
15                 }
16             }
17         }
18         pq.sort(by:{return $0[2] < $1[2]})
19         var last_i:Int = 0
20         var last_j:Int = 0
21         var result:Int = 0
22         while (!pq.isEmpty)
23         {
24             var new_step:[Int] = pq.removeFirst()
25             var step:Int = bfs(&forest, last_i, last_j, new_step[0], new_step[1])
26             if step == -1 {return -1}
27             result += step
28             last_i = new_step[0]
29             last_j = new_step[1]
30         }
31         return result
32     }
33         
34     func bfs(_ forest:inout [[Int]],_ start_i:Int,_ start_j:Int,_ end_i:Int,_ end_j:Int) -> Int
35     {
36         var queue:[[Int]] = [[Int]]()
37         var m:Int = forest.count
38         var n:Int = forest[0].count
39         var visited:[[Bool]] = [[Bool]](repeating:[Bool](repeating:false,count:n),count:m)
40         queue.append([start_i, start_j])
41         var level:Int = 0
42         while(!queue.isEmpty)
43         {
44             var size:Int = queue.count
45             for i in 0..<size
46             {
47                 var curr:[Int] = queue.removeFirst()
48                 if curr[0] == end_i && curr[1] == end_j
49                 {
50                     return level
51                 }
52                 for j in 0..<4
53                 {
54                     var next_i:Int = curr[0]+dirs[j][0]
55                     var next_j:Int = curr[1]+dirs[j][1]
56                     if inBounds(forest, next_i , next_j) && !visited[next_i][next_j]
57                     {
58                         visited[next_i][next_j] = true
59                         queue.append([next_i, next_j])
60                     }                    
61                 }
62             }
63             level += 1
64         }
65         return -1
66     }
67         
68     func inBounds(_ forest: [[Int]],_ i:Int,_ j:Int) -> Bool
69     {
70         return (i >= 0) && (i <= forest.count-1) 
71         && (j >= 0) && (j <= forest[0].count - 1) && (forest[i][j] != 0)            
72     }        
73 }