本文最后更新于209 天前，其中的信息可能已经过时，如有错误请发送邮件到2446865563@qq.com
1.题目基本信息
1.1.题目描述
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
-
0 表示障碍，无法触碰
-
1 表示地面，可以行走
-
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
1.2.题目地址
https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/
2.解题方法
2.1.解题思路
思路1：BFS求单源最短路径
思路2：Dijkstra算法求单源最短路径
思路3：A*算法求单源最短路径
2.2.解题步骤
思路1：BFS
-
第一步，预处理。将forest中的位置进行一维化，(i,j)的编号为i*n+j，函数bfs获取从结点src到dst的最短距离
-
第二步，根据树高对结点进行排序
-
第三步，对排序后的结点数组进行遍历，计算最短步数
思路2：Dijkstra算法
-
第一步，预处理。将forest中的位置进行一维化，(i,j)的编号为i*n+j，函数dijkstra获取从结点src到dst的最短距离
-
第二步，根据树高对结点进行排序
-
第三步，对排序后的结点数组进行遍历，计算最短步数
思路3：A*算法
-
第一步，预处理。将forest中的位置进行一维化，(i,j)的编号为i*n+j；函数getEstimateDist获取两个结点之间的估计距离，函数astar获取从结点src到dst的最短距离
-
第二步，根据树高对结点进行排序
-
第三步，对排序后的结点数组进行遍历，计算最短步数
3.解题代码
python3代码-BFS求单源最短路径
from collections import deque
from heapq import heappush, heappop
class Solution:
def cutOffTree(self, forest: List[List[int]]) -> int:
# 思路1：BFS求单源最短路径
m, n = len(forest), len(forest[0])
# 第一步，预处理。将forest中的位置进行一维化，(i,j)的编号为i*n+j，函数bfs获取从结点src到dst的最短距离
def bfs(src:int, dst:int) -> int:
que = deque([src])
visited = [False] * (m * n)
visited[src] = True
steps = 0
while que:
size = len(que)
for _ in range(size):
node = que.popleft()
if node == dst:
return steps
r, c = node // n, node % n
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
newNode = nr * n + nc
if 0 <= nr < m and 0 <= nc < n and forest[nr][nc] > 0 and not visited[newNode]:
que.append(newNode)
visited[newNode] = True
steps += 1
return -1
# 第二步，根据树高对结点进行排序
nodes = []
for i in range(m):
for j in range(n):
if forest[i][j] > 1:
nodes.append((forest[i][j], i * n + j))
nodes.sort()
# 第三步，对排序后的结点数组进行遍历，计算最短步数
result = 0
src = 0
for i in range(len(nodes)):
_, node = nodes[i]
steps = bfs(src, node)
if steps < 0:
return -1
result += steps
src = node
return resultpython3代码-Dijkstra算法求单源最短路径
from collections import deque
from heapq import heappush, heappop
class Solution:
def cutOffTree(self, forest: List[List[int]]) -> int:
# 思路2：Dijkstra算法求单源最短路径
m, n = len(forest), len(forest[0])
# 第一步，预处理。将forest中的位置进行一维化，(i,j)的编号为i*n+j，函数dijkstra获取从结点src到dst的最短距离
def dijkstra(src:int, dst:int) -> int:
heap = [(0, src)]
distances = [inf] * (m * n)
distances[src] = 0
while heap:
dist, node = heappop(heap)
if dist > distances[node]:
continue
if dst == node:
return dist
r, c = node // n, node % n
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
neighNode = nr * n + nc
thisDist = distances[node] + 1
if 0 <= nr < m and 0 <= nc < n and forest[nr][nc] > 0 and thisDist < distances[neighNode]:
heappush(heap, (thisDist, neighNode))
distances[neighNode] = thisDist
return -1
# 第二步，根据树高对结点进行排序
nodes = []
for i in range(m):
for j in range(n):
if forest[i][j] > 1:
nodes.append((forest[i][j], i * n + j))
nodes.sort()
# 第三步，对排序后的结点数组进行遍历，计算最短步数
result = 0
src = 0
for i in range(len(nodes)):
_, node = nodes[i]
steps = dijkstra(src, node)
if steps < 0:
return -1
result += steps
src = node
return resultpython3代码-Astar算法求单源最短路径
from collections import deque
from heapq import heappush, heappop
class Solution:
def cutOffTree(self, forest: List[List[int]]) -> int:
# 思路1：A*算法求单源最短路径
m, n = len(forest), len(forest[0])
# 第一步，预处理。将forest中的位置进行一维化，(i,j)的编号为i*n+j；函数getEstimateDist获取两个结点之间的估计距离，函数astar获取从结点src到dst的最短距离
getEstimateDist = lambda node1, node2: abs(node2 // n - node1 // n) + abs(node2 % n - node1 % n)
def astar(src:int, dst:int) -> int:
heap = [(getEstimateDist(src, dst), src)]
distances = [inf] * (m * n)
distances[src] = 0
while heap:
addedDist, node = heappop(heap)
if node == dst:
return distances[node]
r, c = node // n, node % n
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
neighNode = nr * n + nc
thisDist = distances[node] + 1
if 0 <= nr < m and 0 <= nc < n and forest[nr][nc] > 0 and thisDist < distances[neighNode]:
heappush(heap, (thisDist + getEstimateDist(neighNode, dst), neighNode))
distances[neighNode] = thisDist
return -1
# 第二步，根据树高对结点进行排序
nodes = []
for i in range(m):
for j in range(n):
if forest[i][j] > 1:
nodes.append((forest[i][j], i * n + j))
nodes.sort()
# 第三步，对排序后的结点数组进行遍历，计算最短步数
result = 0
src = 0
for i in range(len(nodes)):
_, node = nodes[i]
steps = astar(src, node)
if steps < 0:
return -1
result += steps
src = node
return result4.执行结果
