// 力扣
// 1. 最大值最小 → 二分 + 判定
// 至于连通性判断：搜索 、并查集均可；搜索效率更高。
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func minInt(a, b int) int {
if a < b {
return a
}
return b
}
func absInt(a int) int {
if a < 0 {
return -a
}
return a
}
func findSet(x int, parent []int) int {
if parent[x] < 0 {
return x
}
parent[x] = findSet(parent[x], parent)
return parent[x]
}
func unionSet(x, y int, parent []int) int {
r1, r2 := findSet(x, parent), findSet(y, parent)
if r1 == r2 {
return 0
}
if parent[r1] < parent[r2] {
parent[r1] += parent[r2]
parent[r2] = r1
} else {
parent[r2] += parent[r1]
parent[r1] = r2
}
return 1
}
func minimumEffortPath(heights [][]int) int {
n, m := len(heights), len(heights[0])
parent := make([]int, n*m)
maxH, dx, dy := 0, []int{-1, 1, 0, 0}, []int{0, 0, -1, 1}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
for k := 0; k < 4; k++ {
ii, jj := i + dx[k], j + dy[k]
if ii >= 0 && ii < n && jj >= 0 && jj < m {
maxH = maxInt(maxH, absInt(heights[i][j]-heights[ii][jj]))
}
}
}
}
var check = func(h int) bool {
for i := 0; i < n*m; i++ {
parent[i] = -1
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
for k := 0; k < 4; k++ {
ii, jj := i + dx[k], j + dy[k]
if ii >= 0 && ii < n && jj >= 0 && jj < m && absInt(heights[i][j]-heights[ii][jj]) <= h {
unionSet(i*m+j, ii*m+jj, parent)
}
}
}
}
return findSet(0, parent) == findSet(n*m-1, parent)
}
l, r, ans := 0, maxH, -1
for l <= r {
mid := l + (r-l)/2
if check(mid) {
ans = mid
r = mid - 1
} else {
l = mid + 1
}
}
return ans
}
// 2. 最短路径 → dijkstra + heap 、spfa
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func minInt(a, b int) int {
if a < b {
return a
}
return b
}
func absInt(a int) int {
if a < 0 {
return -a
}
return a
}
func minimumEffortPath(heights [][]int) int {
n, m := len(heights), len(heights[0])
dis := make([]int, n*m)
for i := 1; i < n*m; i++ {
dis[i] = 0x3f3f3f3f
}
dx, dy := []int{-1, 1, 0, 0}, []int{0, 0, -1, 1}
que := make([]int, 0, 1000000)
inq := make([]bool, n*m)
que = append(que, 0)
inq[0] = true
for len(que) > 0 {
u := que[0]
que = que[1:]
inq[u] = false
x, y := u/m, u%m
for i := 0; i < 4; i++ {
xx, yy := x+dx[i], y+dy[i]
if xx >= 0 && xx < n && yy >= 0 && yy < m {
v := xx*m + yy
w := maxInt(dis[u], absInt(heights[x][y]-heights[xx][yy]))
if dis[v] > w {
dis[v] = w
if !inq[v] {
inq[v] = true
que = append(que, v)
}
}
}
}
}
return dis[n*m-1]
}