0675-为高尔夫比赛砍树

Raphael Liu Lv10

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

前言

题目要求从 (0, 0) 开始并按照树的高度大小进行砍树并求出最小步数,假设所有树按照从高度从小到大的排序顺序为 t_1, t_2, t_3, t_4, \cdots, t_n,设 d(x, y) 表示从 x 到 y 之间的步数,设 t_0 = (0, 0) ,则可推出砍树的总的步数为 total} = \sum_{i=0}^{n-1} d(t_i, t_i+1),若使得 total 最小,只需满足所有的 d(i, i+1) 都为最小,即可使得 total 最小,该题即转为求相邻树的两点之间的最短距离。

方法一:广度优先搜索

思路与算法

首先对矩阵中的树按照树的高度进行排序,我们依次求出相邻的树之间的最短距离。利用广度优先搜索,按照层次遍历,处理队列中的节点(网格位置)。visited 记录在某个时间点已经添加到队列中的节点,这些节点已被处理或在等待处理的队列中。对于下一个要处理的每个节点,查看他们的四个方向上相邻的点,如果相邻的点没有被遍历过且不是障碍,将其加入到队列中,直到找到终点为止,返回当前的步数即可。最终返回所有的步数之和即为最终结果。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def cutOffTree(self, forest: List[List[int]]) -> int:
def bfs(sx: int, sy: int, tx: int, ty: int) -> int:
m, n = len(forest), len(forest[0])
q = deque([(0, sx, sy)])
vis = {(sx, sy)}
while q:
d, x, y = q.popleft()
if x == tx and y == ty:
return d
for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
if 0 <= nx < m and 0 <= ny < n and forest[nx][ny] and (nx, ny) not in vis:
vis.add((nx, ny))
q.append((d + 1, nx, ny))
return -1

trees = sorted((h, i, j) for i, row in enumerate(forest) for j, h in enumerate(row) if h > 1)
ans = preI = preJ = 0
for _, i, j in trees:
d = bfs(preI, preJ, i, j)
if d < 0:
return -1
ans += d
preI, preJ = i, j
return ans
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int bfs(vector<vector<int>>& forest, int sx, int sy, int tx, int ty) {
if (sx == tx && sy == ty) {
return 0;
}

int row = forest.size();
int col = forest[0].size();
int step = 0;
queue<pair<int, int>> qu;
vector<vector<bool>> visited(row, vector<bool>(col, false));
qu.emplace(sx, sy);
visited[sx][sy] = true;
while (!qu.empty()) {
step++;
int sz = qu.size();
for (int i = 0; i < sz; ++i) {
auto [cx, cy] = qu.front();
qu.pop();
for (int j = 0; j < 4; ++j) {
int nx = cx + dirs[j][0];
int ny = cy + dirs[j][1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
if (!visited[nx][ny] && forest[nx][ny] > 0) {
if (nx == tx && ny == ty) {
return step;
}
qu.emplace(nx, ny);
visited[nx][ny] = true;
}
}
}
}
}
return -1;
}

int cutOffTree(vector<vector<int>>& forest) {
vector<pair<int, int>> trees;
int row = forest.size();
int col = forest[0].size();
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (forest[i][j] > 1) {
trees.emplace_back(i, j);
}
}
}
sort(trees.begin(), trees.end(), [&](const pair<int, int> & a, const pair<int, int> & b) {
return forest[a.first][a.second] < forest[b.first][b.second];
});

int cx = 0;
int cy = 0;
int ans = 0;
for (int i = 0; i < trees.size(); ++i) {
int steps = bfs(forest, cx, cy, trees[i].first, trees[i].second);
if (steps == -1) {
return -1;
}
ans += steps;
cx = trees[i].first;
cy = trees[i].second;
}
return ans;
}
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public int cutOffTree(List<List<Integer>> forest) {
List<int[]> trees = new ArrayList<int[]>();
int row = forest.size();
int col = forest.get(0).size();
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (forest.get(i).get(j) > 1) {
trees.add(new int[]{i, j});
}
}
}
Collections.sort(trees, (a, b) -> forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]));

int cx = 0;
int cy = 0;
int ans = 0;
for (int i = 0; i < trees.size(); ++i) {
int steps = bfs(forest, cx, cy, trees.get(i)[0], trees.get(i)[1]);
if (steps == -1) {
return -1;
}
ans += steps;
cx = trees.get(i)[0];
cy = trees.get(i)[1];
}
return ans;
}

public int bfs(List<List<Integer>> forest, int sx, int sy, int tx, int ty) {
if (sx == tx && sy == ty) {
return 0;
}

int row = forest.size();
int col = forest.get(0).size();
int step = 0;
Queue<int[]> queue = new ArrayDeque<int[]>();
boolean[][] visited = new boolean[row][col];
queue.offer(new int[]{sx, sy});
visited[sx][sy] = true;
while (!queue.isEmpty()) {
step++;
int sz = queue.size();
for (int i = 0; i < sz; ++i) {
int[] cell = queue.poll();
int cx = cell[0], cy = cell[1];
for (int j = 0; j < 4; ++j) {
int nx = cx + dirs[j][0];
int ny = cy + dirs[j][1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
if (!visited[nx][ny] && forest.get(nx).get(ny) > 0) {
if (nx == tx && ny == ty) {
return step;
}
queue.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
}
return -1;
}
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class Solution {
int[][] dirs = {new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}};

public int CutOffTree(IList<IList<int>> forest) {
List<Tuple<int, int>> trees = new List<Tuple<int, int>>();
int row = forest.Count;
int col = forest[0].Count;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (forest[i][j] > 1) {
trees.Add(new Tuple<int, int>(i, j));
}
}
}
trees.Sort((a, b) => forest[a.Item1][a.Item2] - forest[b.Item1][b.Item2]);

int cx = 0;
int cy = 0;
int ans = 0;
for (int i = 0; i < trees.Count; ++i) {
int steps = BFS(forest, cx, cy, trees[i].Item1, trees[i].Item2);
if (steps == -1) {
return -1;
}
ans += steps;
cx = trees[i].Item1;
cy = trees[i].Item2;
}
return ans;
}

public int BFS(IList<IList<int>> forest, int sx, int sy, int tx, int ty) {
if (sx == tx && sy == ty) {
return 0;
}

int row = forest.Count;
int col = forest[0].Count;
int step = 0;
Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
bool[,] visited = new bool[row, col];
queue.Enqueue(new Tuple<int, int>(sx, sy));
visited[sx, sy] = true;
while (queue.Count > 0) {
step++;
int sz = queue.Count;
for (int i = 0; i < sz; ++i) {
Tuple<int, int> cell = queue.Dequeue();
int cx = cell.Item1, cy = cell.Item2;
for (int j = 0; j < 4; ++j) {
int nx = cx + dirs[j][0];
int ny = cy + dirs[j][1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
if (!visited[nx, ny] && forest[nx][ny] > 0) {
if (nx == tx && ny == ty) {
return step;
}
queue.Enqueue(new Tuple<int, int>(nx, ny));
visited[nx, ny] = true;
}
}
}
}
}
return -1;
}
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
typedef struct {
int x;
int y;
int height;
} Tree;

static int cmp(const void *pa, const void *pb) {
return ((Tree *)pa)->height - ((Tree *)pb)->height;
}

static int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int bfs(const int **forest, int row, int col, int sx, int sy, int tx, int ty) {
if (sx == tx && sy == ty) {
return 0;
}

int step = 0;
int *queue = (int *)malloc(sizeof(int) * row * col);
int *visited = (int *)malloc(sizeof(int) * row * col);
int head = 0, tail = 0;
memset(visited, 0, sizeof(int) * row * col);
queue[tail++] = sx * col + sy;
visited[sx * col + sy] = true;
while (head != tail) {
step++;
int sz = tail - head;
for (int i = 0; i < sz; ++i) {
int cx = queue[head] / col;
int cy = queue[head] % col;
head++;
for (int j = 0; j < 4; ++j) {
int nx = cx + dirs[j][0];
int ny = cy + dirs[j][1];
if ( nx >= 0 && nx < row && ny >= 0 && ny < col) {
if (!visited[nx * col + ny] && forest[nx][ny] > 0) {
if (nx == tx && ny == ty) {
free(queue);
free(visited);
return step;
}
queue[tail++] = nx * col + ny;
visited[nx * col + ny] = true;
}
}
}
}
}
free(queue);
free(visited);
return -1;
}

int cutOffTree(int** forest, int forestSize, int* forestColSize) {
int row = forestSize;
int col = forestColSize[0];
int treeSize = 0;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (forest[i][j] > 1) {
treeSize++;
}
}
}
Tree * trees = (Tree *)malloc(sizeof(Tree) * treeSize);
int pos = 0;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (forest[i][j] > 1) {
trees[pos].x = i;
trees[pos].y = j;
trees[pos].height = forest[i][j];
pos++;
}
}
}
qsort(trees, treeSize, sizeof(Tree), cmp);
int cx = 0;
int cy = 0;
int ans = 0;
for (int i = 0; i < treeSize; ++i) {
int steps = bfs(forest, row, col, cx, cy, trees[i].x, trees[i].y);
if (steps == -1) {
return -1;
}
ans += steps;
cx = trees[i].x;
cy = trees[i].y;
}
return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
var cutOffTree = function(forest) {
const trees = [];
const row = forest.length;
const col = forest[0].length;
for (let i = 0; i < row; ++i) {
for (let j = 0; j < col; ++j) {
if (forest[i][j] > 1) {
trees.push([i, j]);
}
}
}
trees.sort((a, b) => forest[a[0]][a[1]] - forest[b[0]][b[1]]);

let cx = 0;
let cy = 0;
let ans = 0;
for (let i = 0; i < trees.length; ++i) {
let steps = bfs(forest, cx, cy, trees[i][0], trees[i][1]);
if (steps === -1) {
return -1;
}
ans += steps;
cx = trees[i][0];
cy = trees[i][1];
}
return ans;
};

const bfs = (forest, sx, sy, tx, ty) => {
if (sx === tx && sy === ty) {
return 0;
}

const row = forest.length;
const col = forest[0].length;
let step = 0;
const queue = [];
const visited = new Array(row).fill(0).map(() => new Array(col).fill(0));
queue.push([sx, sy]);
visited[sx][sy] = true;
while (queue.length) {
step++;
const sz = queue.length;
for (let i = 0; i < sz; ++i) {
const cell = queue.shift();
const cx = cell[0], cy = cell[1];
for (let j = 0; j < 4; ++j) {
const nx = cx + dirs[j][0];
const ny = cy + dirs[j][1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
if (!visited[nx][ny] && forest[nx][ny] > 0) {
if (nx === tx && ny === ty) {
return step;
}
queue.push([nx, ny]);
visited[nx][ny] = true;
}
}
}
}
}
return -1;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
var dir4 = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func cutOffTree(forest [][]int) (ans int) {
type pair struct{ dis, x, y int }
trees := []pair{}
for i, row := range forest {
for j, h := range row {
if h > 1 {
trees = append(trees, pair{h, i, j})
}
}
}
sort.Slice(trees, func(i, j int) bool { return trees[i].dis < trees[j].dis })

bfs := func(sx, sy, tx, ty int) int {
m, n := len(forest), len(forest[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
vis[sx][sy] = true
q := []pair{{0, sx, sy}}
for len(q) > 0 {
p := q[0]
q = q[1:]
if p.x == tx && p.y == ty {
return p.dis
}
for _, d := range dir4 {
if x, y := p.x+d.x, p.y+d.y; 0 <= x && x < m && 0 <= y && y < n && !vis[x][y] && forest[x][y] > 0 {
vis[x][y] = true
q = append(q, pair{p.dis + 1, x, y})
}
}
}
return -1
}

preX, preY := 0, 0
for _, t := range trees {
d := bfs(preX, preY, t.x, t.y)
if d < 0 {
return -1
}
ans += d
preX, preY = t.x, t.y
}
return
}

复杂度分析

  • 时间复杂度:O(m^2 \times n^2),其中 m 为矩阵的行数,n 为矩阵的列数。矩阵中最多有 m \times n 颗树,对树的高度进行排序,时间复杂度为 O(m \times n \times \log (m \times n)),利用广度优先搜索两颗树之间的最短距离需要的时间为 O(m \times n),因此总的时间复杂为 O(m \times n \times \log (m \times n) + m^2 \times n^2) = O(m^2 \times n^2) 。

  • 空间复杂度:O(m \times n),其中 m 为矩阵的行数,n 为矩阵的列数。矩阵中最多有 m \times n 颗树,对树的高度进行排序,所需要的栈空间为 O(\log (m \times n)),利用广度优先搜索队列中最多有 O(m \times n) 个元素,标记已遍历过的元素需要的空间为 O(m \times n),因此总的空间复杂度为 O(m \times n)。

方法二:Dijkstra 算法

思路与算法

我们还可以利用 Dijkstra 算法求矩阵中两点的最短距离,Dijkstra 算法也是利用的广度优先搜索,不同的是,每次对队列中优先选择最短路径的元素。visited 记录在某个时间点已经添加到队列中的节点,这些节点已被处理或在等待处理的队列中。每次从队列中取出当前从起点开始的最少步数的点,对于下一个要处理的每个节点,查看他们的四个方向上相邻的点,如果相邻的点没有被遍历过且不是障碍,将其加入到队列中,直到找到终点为止,返回当前的步数即可。最终返回所有的步数之和即为最终结果。
使用该算法需要考虑的问题:由于题目中遇到障碍物无法通行的,因此当前选择的最短路径的节点并不是最优的,所以该解法在此题中性能不太好。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int bfs(vector<vector<int>>& forest, int sx, int sy, int tx, int ty) {
if (sx == tx && sy == ty) {
return 0;
}

int row = forest.size();
int col = forest[0].size();
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<vector<bool>> visited(row, vector<bool>(col, false));
pq.emplace(0, sx * col + sy);
visited[sx][sy] = true;
while (!pq.empty()) {
auto [dist, loc] = pq.top();
pq.pop();
for (int j = 0; j < 4; ++j) {
int nx = loc / col + dirs[j][0];
int ny = loc % col + dirs[j][1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
if (!visited[nx][ny] && forest[nx][ny] > 0) {
if (nx == tx && ny == ty) {
return dist + 1;
}
pq.emplace(dist + 1, nx * col + ny);
visited[nx][ny] = true;
}
}
}
}
return -1;
}

int cutOffTree(vector<vector<int>>& forest) {
vector<pair<int, int>> trees;
int row = forest.size();
int col = forest[0].size();
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (forest[i][j] > 1) {
trees.emplace_back(i, j);
}
}
}
sort(trees.begin(), trees.end(), [&](const pair<int, int> & a, const pair<int, int> & b) {
return forest[a.first][a.second] < forest[b.first][b.second];
});

int cx = 0;
int cy = 0;
int ans = 0;
for (int i = 0; i < trees.size(); ++i) {
int steps = bfs(forest, cx, cy, trees[i].first, trees[i].second);
if (steps == -1) {
return -1;
}
ans += steps;
cx = trees[i].first;
cy = trees[i].second;
}
return ans;
}
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public int cutOffTree(List<List<Integer>> forest) {
List<int[]> trees = new ArrayList<int[]>();
int row = forest.size();
int col = forest.get(0).size();
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (forest.get(i).get(j) > 1) {
trees.add(new int[]{i, j});
}
}
}
Collections.sort(trees, (a, b) -> forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]));

int cx = 0;
int cy = 0;
int ans = 0;
for (int i = 0; i < trees.size(); ++i) {
int steps = bfs(forest, cx, cy, trees.get(i)[0], trees.get(i)[1]);
if (steps == -1) {
return -1;
}
ans += steps;
cx = trees.get(i)[0];
cy = trees.get(i)[1];
}
return ans;
}

public int bfs(List<List<Integer>> forest, int sx, int sy, int tx, int ty) {
if (sx == tx && sy == ty) {
return 0;
}

int row = forest.size();
int col = forest.get(0).size();
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
boolean[][] visited = new boolean[row][col];
pq.offer(new int[]{0, sx * col + sy});
visited[sx][sy] = true;
while (!pq.isEmpty()) {
int[] arr = pq.poll();
int dist = arr[0], loc = arr[1];
for (int j = 0; j < 4; ++j) {
int nx = loc / col + dirs[j][0];
int ny = loc % col + dirs[j][1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
if (!visited[nx][ny] && forest.get(nx).get(ny) > 0) {
if (nx == tx && ny == ty) {
return dist + 1;
}
pq.offer(new int[]{dist + 1, nx * col + ny});
visited[nx][ny] = true;
}
}
}
}
return -1;
}
}

复杂度分析

  • 时间复杂度:O(m^2 \times n^2 \times \log (m \times n)),其中 m 为矩阵的行数,n 为矩阵的列数。矩阵中最多有 m \times n 颗树,对树的高度进行排序,时间复杂度为 O(m \times n \times \log (m \times n)),利用 Dijkstra 求最短距离需要的时间为 O(m \times n \times \log (m \times n)),因此总的时间复杂为 O(m \times n \times \log (m \times n) + m^2 \times n^2 \times \log (m \times n)) = O(m^2 \times n^2 \times \log (m \times n)) 。

  • 空间复杂度:O(m \times n),其中 m 为矩阵的行数,n 为矩阵的列数。矩阵中最多有 m \times n 颗树,对树的高度进行排序,所需要的栈空间为 O(\log (m \times n)),利用 Dijkstra 算法队列中最多有 O(m \times n) 个元素,标记已遍历过的元素需要的空间为 O(m \times n),因此总的空间复杂度为 O(m \times n)。

方法三:A* 启发式搜索算法

思路与算法

A* 算法 」算法是另一种路径查找算法。设当前搜索的起点为 (\textit{sx}, \textit{sy}),终点为 (\textit{tx}, \textit{ty}), 对于位置 (x, y) 的每个节点,设 A* 的估算函数为 f(x, y) = g(x, y) + h(x, y),其中 g(x, y) 表示从起点 (\textit{sx}, \textit{sy}) 到 (x, y) 的实际距离,评估函数 h(x, y) 在此选择 (x, y) 到 (\textit{tx}, \textit{ty}) 的曼哈顿距离。

我们利用优先队列优先选择估算函数值最小的节点,实际上 A* 搜索是 Dijkstra 的一个特例,当评估函数的 h(x, y) = 0 时,此时该算法即为 Dijkstra 搜索。

代码

[sol3-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int bfs(vector<vector<int>>& forest, int sx, int sy, int tx, int ty) {
if (sx == tx && sy == ty) {
return 0;
}

int row = forest.size();
int col = forest[0].size();
vector<vector<int>> costed(row, vector<int>(col, INT_MAX));
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
costed[sx][sy] = abs(sx - tx) + abs(sy - ty);
pq.emplace(costed[sx][sy], 0, sx * col + sy);
while (!pq.empty()) {
auto [cost, dist, loc] = pq.top();
pq.pop();
int cx = loc / col;
int cy = loc % col;
if (cx == tx && cy == ty) {
return dist;
}
for (int i = 0; i < 4; ++i) {
int nx = cx + dirs[i][0];
int ny = cy + dirs[i][1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col && forest[nx][ny] > 0) {
int ncost = dist + 1 + abs(nx - tx) + abs(ny - ty);
if (ncost < costed[nx][ny]) {
pq.emplace(ncost, dist + 1, nx * col + ny);
costed[nx][ny] = ncost;
}
}
}
}
return -1;
}

int cutOffTree(vector<vector<int>>& forest) {
vector<pair<int, int>> trees;
int row = forest.size();
int col = forest[0].size();
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (forest[i][j] > 1) {
trees.emplace_back(i, j);
}
}
}
sort(trees.begin(), trees.end(), [&](const pair<int, int> & a, const pair<int, int> & b) {
return forest[a.first][a.second] < forest[b.first][b.second];
});

int cx = 0;
int cy = 0;
int ans = 0;
for (int i = 0; i < trees.size(); ++i) {
int steps = bfs(forest, cx, cy, trees[i].first, trees[i].second);
if (steps == -1) {
return -1;
}
ans += steps;
cx = trees[i].first;
cy = trees[i].second;
}
return ans;
}
};
[sol3-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public int cutOffTree(List<List<Integer>> forest) {
List<int[]> trees = new ArrayList<int[]>();
int row = forest.size();
int col = forest.get(0).size();
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (forest.get(i).get(j) > 1) {
trees.add(new int[]{i, j});
}
}
}
Collections.sort(trees, (a, b) -> forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]));

int cx = 0;
int cy = 0;
int ans = 0;
for (int i = 0; i < trees.size(); ++i) {
int steps = bfs(forest, cx, cy, trees.get(i)[0], trees.get(i)[1]);
if (steps == -1) {
return -1;
}
ans += steps;
cx = trees.get(i)[0];
cy = trees.get(i)[1];
}
return ans;
}

public int bfs(List<List<Integer>> forest, int sx, int sy, int tx, int ty) {
if (sx == tx && sy == ty) {
return 0;
}

int row = forest.size();
int col = forest.get(0).size();
int[][] costed = new int[row][col];
for (int i = 0; i < row; ++i) {
Arrays.fill(costed[i], Integer.MAX_VALUE);
}
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
costed[sx][sy] = Math.abs(sx - tx) + Math.abs(sy - ty);
pq.offer(new int[]{costed[sx][sy], 0, sx * col + sy});
while (!pq.isEmpty()) {
int[] arr = pq.poll();
int cost = arr[0], dist = arr[1], loc = arr[2];
int cx = loc / col;
int cy = loc % col;
if (cx == tx && cy == ty) {
return dist;
}
for (int i = 0; i < 4; ++i) {
int nx = cx + dirs[i][0];
int ny = cy + dirs[i][1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col && forest.get(nx).get(ny) > 0) {
int ncost = dist + 1 + Math.abs(nx - tx) + Math.abs(ny - ty);
if (ncost < costed[nx][ny]) {
pq.offer(new int[]{ncost, dist + 1, nx * col + ny});
costed[nx][ny] = ncost;
}
}
}
}
return -1;
}
}

复杂度分析

启发式搜索不讨论时空复杂度。

 Comments
On this page
0675-为高尔夫比赛砍树