大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

题意很模糊，你可能没读懂！！

让我们砍树（数值大于 1 的是树🌲），但是砍树有个规则，必须从低向高砍，问砍完所有树的移动步数。

题目给出的示例不够清晰。看看我下面这几张图，应该秒懂了。

解题方法

分析

根据题意，总的移动步数为：从起点到最低的树的最少步数 + 从最低的树到第 2 低的树的最少步数 + 从第 2 低的树到第 3 低的树的最少步数 + … 直至所有树被砍完。

用图表示就是如下：

求最少移动步数，一般可以使用 BFS 去做。

分享 BFS 模板：

BFS使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。

BFS总共有两个模板：

模板一：

如果不需要确定当前遍历到了哪一层，只需要访问完所有节点就可以时。

BFS 模板如下：

  1. while queue 不空：
  2.     cur = queue.pop()
  3.     if cur 有效且未被访问过：
  4.         进行处理
  5.     for 节点 in cur 的所有相邻节点：
  6.         if 该节点有效：
  7.             queue.push(该节点)

模板二：

如果要确定当前遍历到了哪一层，需要知道最少移动步数时，BFS 模板如下。

这里增加了 level 表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size 表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。

  1. level = 0
  2. while queue 不空：
  3.     size = queue.size()
  4.     while (size --) {
  5.         cur = queue.pop()
  6.         if cur 有效且未被访问过：
  7.             进行处理
  8.         for 节点 in cur的所有相邻节点：
  9.             if 该节点有效：
  10.                 queue.push(该节点)
  11.     }
  12.     level ++;

上面两个是通用模板，在任何题目中都可以用，是要理解并且记住的！

本题需要知道求最少步数，因此使用模板二。

代码

  1. class Solution:
  2.     def cutOffTree(self, forest: List[List[int]]) -> int:
  3.         M = len(forest)
  4.         N = len(forest[0])
  5.         trees = []
  6.         for i in range(M):
  7.             for j in range(N):
  8.                 if (forest[i][j] > 1):
  9.                     trees.append((forest[i][j], i, j))
  10.         trees.sort()
  11.         preX, preY = 0, 0
  12.         res = 0
  13.         for height, curX, curY in trees:
  14.             steps = self.bfs(forest, preX, preY, curX, curY)
  15.             if steps == -1:
  16.                 return -1
  17.             res += steps
  18.             preX, preY = curX, curY
  19.         return res
  21.     def bfs(self, forest, startX, startY, targetX, targetY):
  22.         M = len(forest)
  23.         N = len(forest[0])
  24.         dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
  25.         steps = 0
  26.         queue = collections.deque()
  27.         queue.append((startX, startY))
  28.         visited = set()
  29.         visited.add((startX, startY))
  30.         while queue:
  31.             size = len(queue)
  32.             for _ in range(size):
  33.                 curX, curY = queue.popleft()
  34.                 if curX == targetX and curY == targetY:
  35.                     return steps
  36.                 for d in dirs:
  37.                     nX = curX + d[0]
  38.                     nY = curY + d[1]
  39.                     if 0 <= nX < M and 0 <= nY < N and forest[nX][nY] != 0 and ((nX, nY) not in visited):
  40.                         queue.append((nX, nY))
  41.                         visited.add((nX, nY))
  42.             steps += 1
  43.         return -1

复杂度

  • 时间复杂度：675. 为高尔夫比赛砍树 - 图1，可能有 675. 为高尔夫比赛砍树 - 图2棵树，每次移动最多 675. 为高尔夫比赛砍树 - 图3次。
  • 空间复杂度：675. 为高尔夫比赛砍树 - 图4。

总结

  1. 理解题意啊！！

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。