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^9
- 所有树的高度都不相同。
解题思路
这是一个典型的图论问题，需要结合排序和 BFS 来解决。
核心思路：
- 首先收集所有树木的位置和高度，并按高度从小到大排序
- 从起点 (0,0) 开始，依次走到每棵树的位置并砍掉
- 每次移动都使用 BFS 寻找从当前位置到目标位置的最短路径
- 累加所有移动步数作为最终答案
详细步骤：
- 遍历矩阵，将所有大于 1 的树木信息（高度、行、列）存入数组并排序
- 设置当前位置为起点 (0,0)，总步数为 0
- 对于排序后的每棵树，使用 BFS 计算从当前位置到该树位置的最短距离
- 如果无法到达某棵树，返回 -1
- 累加距离到总步数，更新当前位置为该树的位置
- 所有树砍完后返回总步数
BFS 实现要点：
- 使用队列存储待访问的位置
- 使用访问标记避免重复访问
- 四个方向进行扩展：上下左右
- 遇到障碍物（值为 0）或越界时跳过
时间复杂度主要由树木数量和 BFS 搜索决定，空间复杂度由 BFS 队列和访问标记决定。
代码实现
class Solution {
public:
int cutOffTree(vector<vector<int>>& forest) {
int m = forest.size(), n = forest[0].size();
// 收集所有树木并按高度排序
vector<vector<int>> trees;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (forest[i][j] > 1) {
trees.push_back({forest[i][j], i, j});
}
}
}
sort(trees.begin(), trees.end());
// 从起点到目标点的最短距离
auto bfs = [&](int sr, int sc, int tr, int tc) -> int {
if (sr == tr && sc == tc) return 0;
queue<pair<int, int>> q;
vector<vector<bool>> visited(m, vector<bool>(n, false));
q.push({sr, sc});
visited[sr][sc] = true;
int steps = 0;
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!q.empty()) {
int size = q.size();
steps++;
for (int i = 0; i < size; i++) {
auto [r, c] = q.front();
q.pop();
for (int j = 0; j < 4; j++) {
int nr = r + dirs[j][0];
int nc = c + dirs[j][1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
!visited[nr][nc] && forest[nr][nc] != 0) {
if (nr == tr && nc == tc) return steps;
visited[nr][nc] = true;
q.push({nr, nc});
}
}
}
}
return -1;
};
int sr = 0, sc = 0, totalSteps = 0;
for (auto& tree : trees) {
int steps = bfs(sr, sc, tree[1], tree[2]);
if (steps == -1) return -1;
totalSteps += steps;
sr = tree[1];
sc = tree[2];
}
return totalSteps;
}
};
class Solution:
def cutOffTree(self, forest: List[List[int]]) -> int:
m, n = len(forest), len(forest[0])
# 收集所有树木并按高度排序
trees = []
for i in range(m):
for j in range(n):
if forest[i][j] > 1:
trees.append((forest[i][j], i, j))
trees.sort()
def bfs(sr, sc, tr, tc):
if sr == tr and sc == tc:
return 0
queue = collections.deque([(sr, sc)])
visited = set()
visited.add((sr, sc))
steps = 0
while queue:
steps += 1
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if (0 <= nr < m and 0 <= nc < n and
(nr, nc) not in visited and forest[nr][nc] != 0):
if nr == tr and nc == tc:
return steps
visited.add((nr, nc))
queue.append((nr, nc))
return -1
sr, sc = 0, 0
total_steps = 0
for _, tr, tc in trees:
steps = bfs(sr, sc, tr, tc)
if steps == -1:
return -1
total_steps += steps
sr, sc = tr, tc
return total_steps
public class Solution {
public int CutOffTree(IList<IList<int>> forest) {
int m = forest.Count, n = forest[0].Count;
// 收集所有树木并按高度排序
var trees = new List<(int height, int row, int col)>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (forest[i][j] > 1) {
trees.Add((forest[i][j], i, j));
}
}
}
trees.Sort();
int BFS(int sr, int sc, int tr, int tc) {
if (sr == tr && sc == tc) return 0;
var queue = new Queue<(int, int)>();
var visited = new HashSet<(int, int)>();
queue.Enqueue((sr, sc));
visited.Add((sr, sc));
int steps = 0;
int[,] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (queue.Count > 0) {
int size = queue.Count;
steps++;
for (int i = 0; i < size; i++) {
var (r, c) = queue.Dequeue();
for (int j = 0; j < 4; j++) {
int nr = r + dirs[j, 0];
int nc = c + dirs[j, 1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
!visited.Contains((nr, nc)) && forest[nr][nc] != 0) {
if (nr == tr && nc == tc) return steps;
visited.Add((nr, nc));
queue.Enqueue((nr, nc));
}
}
}
}
return -1;
}
int sr = 0, sc = 0, totalSteps = 0;
foreach (var (_, tr, tc) in trees) {
int steps = BFS(sr, sc, tr, tc);
if (steps == -1) return -1;
totalSteps += steps;
sr = tr;
sc = tc;
}
return totalSteps;
}
}
var cutOffTree = function(forest) {
const m = forest.length;
const n = forest[0].length;
// Collect all trees and sort by height
const trees = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (forest[i][j] > 1) {
trees.push([forest[i][j], i, j]);
}
}
}
trees.sort((a, b) => a[0] - b[0]);
// BFS to find shortest path between two points
const bfs = (startRow, startCol, endRow, endCol) => {
if (startRow === endRow && startCol === endCol) return 0;
const queue = [[startRow, startCol, 0]];
const visited = new Set();
visited.add(`${startRow},${startCol}`);
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
while (queue.length > 0) {
const [row, col, steps] = queue.shift();
for (const [dr, dc] of dirs) {
const newRow = row + dr;
const newCol = col + dc;
const key = `${newRow},${newCol}`;
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
forest[newRow][newCol] !== 0 && !visited.has(key)) {
if (newRow === endRow && newCol === endCol) {
return steps + 1;
}
visited.add(key);
queue.push([newRow, newCol, steps + 1]);
}
}
}
return -1;
};
let totalSteps = 0;
let currentRow = 0, currentCol = 0;
// Cut trees in order
for (const [height, treeRow, treeCol] of trees) {
const steps = bfs(currentRow, currentCol, treeRow, treeCol);
if (steps === -1) return -1;
totalSteps += steps;
currentRow = treeRow;
currentCol = treeCol;
forest[treeRow][treeCol] = 1; // Cut the tree
}
return totalSteps;
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(T × M × N) | T 为树木数量，每次 BFS 最坏需要遍历整个矩阵 |
| 空间复杂度 | O(M × N) | BFS 队列和访问标记数组的空间开销 |