为高尔夫比赛砍树

标签: 广度优先搜索数组矩阵堆（优先队列）

难度: Hard

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示，在这个矩阵中：

0 表示障碍，无法触碰
1 表示地面，可以行走
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

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

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

示例 1：

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

示例 2：

输入：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⁹

Submission

运行时间: 3846 ms

内存: 16.6 MB

from collections import deque
from typing import List

class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        if not forest or not forest[0]:
            return -1
        
        m, n = len(forest), len(forest[0])
        trees = []
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # right, left, down, up
        
        # get all the trees' positions and heights
        for i in range(m):
            for j in range(n):
                if forest[i][j] > 1:
                    trees.append((forest[i][j], i, j))
        
        # if there is no tree, return -1
        if not trees:
            return -1
        
        # sort the trees by their heights
        trees.sort()
        
        # bfs function
        def bfs(sx, sy, tx, ty):
            queue = deque([(sx, sy, 0)])  # (x, y, steps)
            visited = [[False] * n for _ in range(m)]
            visited[sx][sy] = True
            
            while queue:
                x, y, steps = queue.popleft()
                
                if x == tx and y == ty:
                    return steps
                
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and forest[nx][ny] != 0:
                        visited[nx][ny] = True
                        queue.append((nx, ny, steps + 1))
            
            return -1
        
        # initial position
        sx, sy = 0, 0
        total_steps = 0
        
        # cut the trees from the lowest to the highest
        for _, tx, ty in trees:
            steps = bfs(sx, sy, tx, ty)
            
            # if we cannot reach the tree, return -1
            if steps == -1:
                return -1
            
            total_steps += steps
            sx, sy = tx, ty
        
        return total_steps

Explain

这个题解采用了BFS算法来解决问题。首先，我们获取森林中所有树的坐标和高度，并按高度从低到高排序。然后，从起点(0, 0)开始，依次砍掉每棵树。为了找到从当前位置到目标树的最短路径，我们使用BFS搜索。如果无法到达某棵树，则返回-1。否则，累加每次砍树所需的步数，直到砍完所有的树。最后返回总步数。

时间复杂度: O(k log k + k * mn)

空间复杂度: O(k + mn)

from collections import deque
from typing import List

class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        if not forest or not forest[0]:
            return -1
        
        m, n = len(forest), len(forest[0])
        trees = []
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # right, left, down, up
        
        # get all the trees' positions and heights
        for i in range(m):
            for j in range(n):
                if forest[i][j] > 1:
                    trees.append((forest[i][j], i, j))
        
        # if there is no tree, return -1
        if not trees:
            return -1
        
        # sort the trees by their heights
        trees.sort()
        
        # bfs function
        def bfs(sx, sy, tx, ty):
            queue = deque([(sx, sy, 0)])  # (x, y, steps)
            visited = [[False] * n for _ in range(m)]
            visited[sx][sy] = True
            
            while queue:
                x, y, steps = queue.popleft()
                
                if x == tx and y == ty:
                    return steps
                
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and forest[nx][ny] != 0:
                        visited[nx][ny] = True
                        queue.append((nx, ny, steps + 1))
            
            return -1
        
        # initial position
        sx, sy = 0, 0
        total_steps = 0
        
        # cut the trees from the lowest to the highest
        for _, tx, ty in trees:
            steps = bfs(sx, sy, tx, ty)
            
            # if we cannot reach the tree, return -1
            if steps == -1:
                return -1
            
            total_steps += steps
            sx, sy = tx, ty
        
        return total_steps

Explore

题解通过使用广度优先搜索（BFS）来确保从当前位置到下一棵树的最短路径。如果一棵树被障碍物完全包围（即没有可通行的路径到达该树），BFS将返回-1。这意味着如果我们无法到达一棵树，算法会立即返回-1并停止执行，表明不可能砍到所有的树。因此，该算法确保只有在所有树都可以被访问和砍掉时，才会返回总步数。

BFS搜索是一种用于找到从起点到终点的最短路径的算法，其特性是按层级（即步数）展开搜索。使用队列（先进先出的数据结构）正是为了保持这种层级扩展，从而可以逐层遍历所有可能的路径。如果使用栈（后进先出），则变成了深度优先搜索（DFS），这通常不保证找到最短路径。使用优先队列的话，适用于需要根据特定优先级顺序处理节点的情况，例如在Dijkstra算法中处理最短路径问题，但在本题中，我们只需找到任意可达路径的最短距离，因此普通队列足矣。

是的，每次使用BFS搜索新的树时，我们需要重置visited数组。这是因为BFS完成后，visited数组的状态会反映出从起始点到达终点时经过的路径，这些信息是特定于那一次搜索的。为了确保每次搜索都是从新的起点开始，不受之前搜索路径的影响，我们需要在每次树的搜索之前重置visited数组。

如果起始点(0, 0)是障碍物（即forest[0][0]为0），则无法开始砍树的任务，因为没有有效的起点。这种情况下，算法应该立即返回-1，表示任务无法开始。如果(0, 0)是一棵树，则可以正常开始任务，以这棵树作为第一棵需要砍伐的树（如果它不是最矮的树，仍然需要按照高度排序后的顺序进行砍伐）。总之，起始点必须是可通行的，否则任务无法执行。