# LeetCode: 1102. 得分最高的路径¶

## 1、题目描述¶

输入：[[5,4,5],[1,2,6],[7,4,6]]



输入：[[2,2,1,2,2,2],[1,2,2,2,1,2]]



输入：[[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]



• $1 <= R, C <= 100$
• $0 <= A[i][j] <= 10^9$

## 2、解题思路¶

• 使用并查集
• 首先将可能的路径进行排序，每条路径连接两个点，路径值就是这两个点之间的最小值
• 判断左上节点和右下节点能够在一个集合的时候，返回当前的路径值
from typing import List

class DFU:
def __init__(self, length):
self.data = list(range(length))

def find(self, x):
if self.data[x] != x:
self.data[x] = self.find(self.data[x])
return self.data[x]

def union(self, x, y):
xp = self.find(x)
yp = self.find(y)
if xp != yp:
self.data[xp] = yp

def count(self):
res = 0
for index, i in enumerate(self.data):
if index == i:
res += 1
return res

class Solution:
def maximumMinimumPath(self, A: List[List[int]]) -> int:
row, col = len(A), len(A[0])
if row == 1 and col == 1:
return A[0][0]
paths = []
d = DFU(row * col)
start = 0
end = row * col - 1
for i in range(row):
for j in range(col):
if i - 1 >= 0:
paths.append([min(A[i][j], A[i - 1][j]), i * col + j, (i - 1) * col + j])
if j - 1 >= 0:
paths.append([min(A[i][j], A[i][j - 1]), i * col + j, i * col + j - 1])
for val, x, y in sorted(paths, reverse=True):
if d.find(x) != d.find(y):
d.union(x, y)
if d.find(start) == d.find(end):
return val