[LeetCode解题报告] 675. 为高尔夫比赛砍树

一、 题目

1. 题目描述

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 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] <= 109

二、 解题报告

1. 思路分析

这题比较简单，把树预先按树高排序，然后从低到矮搜步长即可。
数据较弱，朴素DFS竟然比A*快。
另外，可以预先用并查集处理砍不完的情况，任一点不和(0,0)连通则不能砍完。

2. 复杂度分析

最坏时间复杂度O(n²m²)

3. 代码实现

搜索。

class PriorityQueue:def __init__(self):self._queue = []self._index = 0  # 传入顺序def push(self, item, priority):# 传入两个参数，一个是存放元素的数组，另一个是要存储的元素，这里是一个元组。heapq.heappush(self._queue, (priority, self._index, item))self._index += 1def pop(self):return heapq.heappop(self._queue)[-1]def __str__(self):return str(self._queue)def __len__(self):return len(self._queue)class Solution:def cutOffTree(self, forest: List[List[int]]) -> int:m, n = len(forest), len(forest[0])if forest[0][0] == 0:return -1fathers = [[(0, 0)] * n for _ in range(m)]  # 并查集trees = [(0, 0, 0)]floors = set()for i in range(m):for j in range(n):h = forest[i][j]fathers[i][j] = (i, j)if h > 1:trees.append((h, i, j))if h > 0:floors.add((i, j))trees.sort()# print(fathers)def find_father(x, y):x1, y1 = fathers[x][y]if (x1, y1) != (x, y):fathers[x][y] = find_father(x1, y1)  # 压缩路径return fathers[x][y]for i in range(m):for j in range(n):if forest[i][j] == 0:continuefor x, y in [(i - 1, j), (i, j - 1)]:if (x, y) not in floors:continuex1, y1 = find_father(x, y)fathers[x1][y1] = find_father(i, j)for i, j in floors:if find_father(0, 0) != find_father(i, j):# print(i,j, find_father(i,j))return -1     def manhadun(x1, y1, x2, y2):return abs(x1 - x2) + abs(y1 - y2)def bfs(x, y, x_tar, y_tar):if x == x_tar and y == y_tar:return 0visited = set()q = PriorityQueue()q.push((x, y, 0), manhadun(x, y, x_tar, y_tar))# q.push((x,y,0),(0,manhadun(x,y,x_tar,y_tar)))# q.push((x,y,0),0)visited.add((x, y))while q:x, y, step = q.pop()if x == x_tar and y == y_tar:return stepfor x1, y1 in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:if (x1, y1) not in floors or (x1, y1) in visited:continue# q.push((x1,y1,step+1),step+1)# q.push((x1,y1,step+1),(step+1,manhadun(x1,y1,x_tar,y_tar)))q.push((x1, y1, step + 1), (step + 1, manhadun(x1, y1, x_tar, y_tar) + step + 1))visited.add((x1, y1))return -1def bfs2(x, y, x_tar, y_tar):if x == x_tar and y == y_tar:return 0visited = set()q = deque()q.append((x, y, 0))visited.add((x, y))while q:x, y, step = q.popleft()if x == x_tar and y == y_tar:return stepfor x1, y1 in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:if (x1, y1) not in floors or (x1, y1) in visited:continue# q.push((x1,y1,step+1),step+1)# q.push((x1,y1,step+1),(step+1,manhadun(x1,y1,x_tar,y_tar)))q.append((x1, y1, step + 1))visited.add((x1, y1))return -1ans = 0for i in range(1, len(trees)):h1, x1, y1 = trees[i - 1]h2, x2, y2 = trees[i]r = bfs(x1, y1, x2, y2)if r == -1:return -1ans += rreturn ans

三、 本题小结

1. A*估价函数要注意是f=g+h，起点终点都要算