1631 最小体力消耗路径：你准备参加一场远足活动。给你一个二维 rows x cols 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0)，且你希望去最右下角的格子 (rows-1, cols-1) （注意下标从 0 开始编号）。你每次可以往上、下、左、右四个方向之一移动，你想要找到耗费体力最小的一条路径。
一条路径耗费的体力值是 路径上相邻格子之间高度差的绝对值的最大值 决定的。请你返回从左上角走到右下角的最小体力消耗值。
1
2
3
4
5
6
7
8
9
| 输入：heights = [
[1,2,1,1,1],
[1,2,1,2,1],
[1,2,1,2,1],
[1,2,1,2,1],
[1,1,1,2,1]
]
输出：0
解释：按着值为 1 的格子走，不需要消耗任何体力。
|
思考
这个题，跟以往常见的移动规则不太一样。常见的是只能向下、向右移动，而此题可以向四个方向移动。如果是只能向下、向右移动，那么可以用动态规划解决，其状态转移方程为：
dp[i][j]=min(max(dp[i−1][j],abs(h[i][j]−h[i−1][j])),max(dp[i][j−1],abs(h[i][j]−h[i][j−1])));
其中，dp[i][j] 表示移动到格子 (i,j) 时消耗的最小体力，它可以从上方的格子到达该格子、也可以从左侧的格子到达该格子。所以 dp[i][j] 会选择两者中体力消耗较少的那个格子作为经过点。
只能向下、向右移动的动态规划解法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int minimumEffortPathRightDown(int** heights, int heightsSize, int* heightsColSize) {
int m = heightsSize, n = *heightsColSize;
int dp[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j > 0) {
dp[i][j] = fmax(dp[i][j - 1], fabs(heights[i][j] - heights[i][j - 1]));
} else if (j == 0 && i > 0) {
dp[i][j] = fmax(dp[i - 1][j], fabs(heights[i][j] - heights[i - 1][j]));
} else if (i > 0 && j > 0){
dp[i][j] = fmin(fmax(dp[i - 1][j], fabs(heights[i][j] - heights[i - 1][j])), fmax(dp[i][j - 1], fabs(heights[i][j] - heights[i][j - 1])));
} else {
dp[0][0] = 0;
}
}
}
return dp[m - 1][n - 1];
}
|
问题转换
我们可以将本题抽象成如下的一个 图论模型：
一般地，「图」中的所有节点的编号都是不一样的。所以我们需要将二维的坐标点，转换成唯一的编号。这可以按 id=rows∗m+cols 来表示。比如，对于 m=4,n=3，从 (3,2) 向上移动到 (2,2) 就是从节点 14 移动到节点 10。
并查集解法
我们可以将地图中的 mn 个格子（节点）放入并查集中，初始时，所有节点各为一个集合。随着「路径的形成」，路径上的节点将会汇集在不同的集合中（不加干预的话，最终所有的点会汇聚成一个集合）。
因此，如果左上角和右下角所对应的节点，被合并到同一个集合内，就可以说明形成了一条从左上角到右下角路径，路径被连通。
但是，我们要找的是一条从左上角到右下角的「最短路径」。所以，我们 可以按边权从小到大的顺序，将这条边的两个点合并到集合中。一旦出现左上角和右下角在同一个集合中，那便是从左上角到右下角的「最短路径」（这次移动的高度差就是首尾连通路径上的最大高度差，但同时也是所有可能的首尾连通路径上的最小高度差）。
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
| typedef struct {
int from;
int to;
int h;
} Edge;
void init(int parent[], int rank[], int size) {
for (int i = 0; i < size; ++i) {
parent[i] = i;
rank[i] = 0;
}
}
int findSet(int parent[], int x) {
if (parent[x] == x) {
return x;
} else {
parent[x] = findSet(parent, parent[x]);
return parent[x];
}
}
void unionSet(int parent[], int rank[], int x, int y) {
int rootX = findSet(parent, x);
int rootY = findSet(parent, y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootX] = rootY;
rank[rootY]++;
}
}
}
int isSameSet(int parent[], int x, int y) {
return findSet(parent, x) == findSet(parent, y);
}
int cmp(const void *pa, const void *pb) {
return ((Edge *)pa)->h - ((Edge *)pb)->h;
}
int minimumEffortPath(int** heights, int heightsSize, int* heightsColSize){
int m = heightsSize, n = *heightsColSize;
if (m * n <= 1) {return 0;}
Edge edgeInfo[m * n * 2];
int edgeSize = 0, id = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j ++) {
id = i * n + j;
if (i < m - 1) {
edgeInfo[edgeSize].from = id;
edgeInfo[edgeSize].to = id + n;
edgeInfo[edgeSize].h = fabs(heights[i][j] - heights[i + 1][j]);
edgeSize++;
}
if (j < n - 1) {
edgeInfo[edgeSize].from = id;
edgeInfo[edgeSize].to = id + 1;
edgeInfo[edgeSize].h = fabs(heights[i][j] - heights[i][j + 1]);
edgeSize++;
}
}
}
qsort(edgeInfo, edgeSize, sizeof(Edge), cmp);
int ufSize = m * n;
int parent[ufSize], rank[ufSize];
init(&parent, &rank, ufSize);
for (int i = 0; i < edgeSize; i++) {
unionSet(&parent, &rank, edgeInfo[i].from, edgeInfo[i].to);
if (isSameSet(&parent, 0, m * n - 1)) {
return edgeInfo[i].h;
}
}
return ~(0x1U << 31);
}
|
本题有多种解法，如二分查找、并查集、dijkstra 算法，有时间再补充。
