- 标签：深度优先搜索、广度优先搜索、并查集、数组、二分查找、矩阵、堆（优先队列）
- 难度：困难
题目大意
#
给定一个 n * n 大小的二维数组 grid，每一个方格的值 grid[i][j] 表示为位置 (i, j) 的高度。
现在要从左上角 (0, 0) 位置出发，经过方格的一些点，到达右下角 (n - 1, n - 1) 位置上。其中所经过路径的花费为这条路径上所有位置的最大高度。
现在要求：计算从 (0, 0) 位置到 (n - 1, n - 1) 的最优路径的花费。
最优路径指的路径上最大高度最小的那条路径。
解题思路
#
将整个网络抽象为一个无向图，每个点与相邻的点（上下左右）之间都存在一条无向边，边的权重为两个点之间的最大高度。
我们要找到左上角到右下角的最优路径，可以遍历所有的点，将所有的边存储到数组中，每条边的存储格式为 [x, y, h]，意思是编号 x 的点和编号为 y 的点之间的权重为 h。
然后按照权重从小到大的顺序，对所有边进行排序。
再按照权重大小遍历所有边，将其依次加入并查集中。并且每次都需要判断 (0, 0) 点和 (n - 1, n - 1) 点是否连通。
如果连通，则该边的权重即为答案。
代码
#
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
|
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.count = n
def find(self, x):
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
self.parent[root_x] = root_y
self.count -= 1
def is_connected(self, x, y):
return self.find(x) == self.find(y)
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
row_size = len(grid)
col_size = len(grid[0])
size = row_size * col_size
edges = []
for row in range(row_size):
for col in range(col_size):
if row < row_size - 1:
x = row * col_size + col
y = (row + 1) * col_size + col
h = max(grid[row][col], grid[row + 1][col])
edges.append([x, y, h])
if col < col_size - 1:
x = row * col_size + col
y = row * col_size + col + 1
h = max(grid[row][col], grid[row][col + 1])
edges.append([x, y, h])
edges.sort(key=lambda x: x[2])
union_find = UnionFind(size)
for edge in edges:
x, y, h = edge[0], edge[1], edge[2]
union_find.union(x, y)
if union_find.is_connected(0, size - 1):
return h
return 0
|