675 为高尔夫比赛砍树（宽搜）

淩亂°似流年 2022-09-02 13:45 177阅读 0赞

**1. 问题描述：**

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：  
0 表示障碍，无法触碰  
1 表示地面，可以行走  
比 1 大的数表示有树的单元格，可以行走，数值表示树的高度每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

**示例 1：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

输入：forest = \[\[1,2,3\],\[0,0,4\],\[7,6,5\]\]  
输出：6  
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

**示例 2：**

![20210803165806420.jpg][]

输入：forest = \[\[1,2,3\],\[0,0,0\],\[7,6,5\]\]  
输出：-1  
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。

**示例 3：**

输入：forest = \[\[2,3,4\],\[0,0,5\],\[8,7,6\]\]  
输出：6  
解释：可以按与示例 1 相同的路径来砍掉所有的树。  
(0,0) 位置的树，可以直接砍去，不用算步数。

**提示：**

m == forest.length  
n == forest\[i\].length  
1 <= m, n <= 50  
0 <= forest\[i\]\[j\] <= 10 ^ 9  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/cut-off-trees-for-golf-event

**2. 思路分析：**

分析题目可以知道我们需要根据树的高度由低到到开始砍，如果发现两个位置之间的树被某些位置阻挡了之后不能够到达说明无法砍完所有的树那么直接返回-1即可，若可以砍完所有的树返回砍完所有树的最少步数。由题可知，从上一个砍树的位置到当前需要砍树的位置是唯一确定的（这是由题目中由树的高度由低到高开始砍决定的），而上一个砍树的位置到当前需要砍树的位置是相互独立的，所以要想使得砍完所有树的操作步数是最少的应该使得砍每一棵树的步数是最少的，也即使得每一个相邻两棵树的位置之间的距离是最短的，根据起点到终点的最短路径的特点我们想到可以使用**宽搜**来解决。首先我们需要将矩阵中所有树的信息加入到列表中，树的信息包括当前树的高度，树的横坐标，纵坐标，因为需要从低到高砍树，所以需要对树由小到大排序，砍每一棵树的时候我们使用宽搜来搜索能否从上一个位置到达当前的位置，也即使用宽搜搜索相邻的两个位置，当不能够到达的时候直接返回-1，否则计算到达当前位置的最短距离即可。

**3. 代码如下：**

from typing import List
    import collections
    
    
    class Solution:
        # 搜索从起点到终点的最短距离, 存在返回最短距离否则返回-1(树的相邻两个位置是否可以到达)
        def bfs(self, start: List[int], end: List[int], forest: List[List[int]]):
            x, y = start[1], start[2]
            # 第一个位置可能是树特判一下直接返回0即可, 这个位置的树可以直接砍掉
            if x == end[1] and y == end[2]: return 0
            r, c = len(forest), len(forest[0])
            # 记录起点到某个位置的最短距离
            dis = [[10 ** 10] * c for i in range(r)]
            dis[x][y] = 0
            # 偏移量列表, 表示上下左右四个方向
            pos = [[1, 0], [-1, 0], [0, 1], [0, -1]]
            # 双端队列
            q = collections.deque([(x, y)])
            while q:
                t = q.popleft()
                for i in range(4):
                    x0 = t[0] + pos[i][0]
                    y0 = t[1] + pos[i][1]
                    # 当前位置不能是障碍所以forests[x0][y0]必须大于0
                    if 0 <= x0 < r and 0 <= y0 < c and forest[x0][y0]:
                        if dis[x0][y0] > dis[t[0]][t[1]] + 1:
                            dis[x0][y0] = dis[t[0]][t[1]] + 1
                            # 加入下一个可以到达的位置
                            q.append((x0, y0))
                            # 判断当前的位置是否是终点如果是终点那么直接返回最短距离即可
                            if x0 == end[1] and y0 == end[2]: return dis[x0][y0]
            return -1
    
        def cutOffTree(self, forest: List[List[int]]) -> int:
            trs = list()
            r, c = len(forest), len(forest[0])
            for i in range(r):
                for j in range(c):
                    # 当前位置大于1说明是树
                    if forest[i][j] > 1:
                        # python使用列表来封装多个属性值, 需要维护三个信息分别是当前位置的值, 当前位置的横坐标, 纵坐标
                        trs.append([forest[i][j], i, j])
            # 因为我们要从高度较低的树到高度较高的树开始砍所以需要先排序, 然后计算相邻两个点是否可以到达即可
            trs.sort()
            # 上一个树的信息
            last = [0, 0, 0]
            res = 0
            for x in trs:
                t = self.bfs(last, x, forest)
                if t == -1:
                    return -1
                last = x
                res += t
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/3ed4dcf058b24191886e9a635a617248.png
[20210803165806420.jpg]: /images/20220829/b362225c3a5f49ce8a78a557ceb81d25.png