1631. 最小体力消耗路径

1631. 最小体力消耗路径

• 难度: medium
• 原始链接: https://leetcode.cn/problems/path-with-minimum-effort
• 标签: 二分查找, 并查集

解法一: 二分查找

go

func minimumEffortPath(heights [][]int) int {
    m := len(heights)
    n := len(heights[0])
    directions := [][]int{
        {0, -1},
        {1, 0},
        {0, 1},
        {-1, 0},
    }
    var dfs func (heights [][]int, visit []bool, r, c, limit int) bool
    dfs = func (heights [][]int, visit []bool, r, c, limit int) bool {
        if visit[r * n + c] {
            return false
        }
        if r == m - 1 && c == n - 1 {
            return true
        }
        visit[r * n + c] = true
        ans := false
        for _, direction := range directions {
            newR := r + direction[0]
            newC := c + direction[1]
            if newR >= 0 && newR < m && newC >= 0 && newC < n && abs(heights[newR][newC] - heights[r][c]) <= limit {
                ans = ans || dfs(heights, visit, newR, newC, limit)
            }
        }
        return ans
    }
    left := 0
    right := 1000000
    for left <= right {
        mid := ((right - left) >> 1) + left
        if dfs(heights, make([]bool, m * n), 0, 0, mid) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
}

func abs(num int) int {
    if num >= 0 {
        return num
    }
    return -num
}

解法二: 并查集

go

func minimumEffortPath(heights [][]int) int {
    m := len(heights)
    n := len(heights[0])
    edges := [][]int{}
    for r, height := range heights {
        for c, num := range height {
            if c + 1 < n {
                edges = append(edges, []int{
                    abs(heights[r][c + 1] - num),
                    r * n + c,
                    r * n + c + 1,
                })
            }
            if r + 1 < m {
                edges = append(edges, []int{
                    abs(heights[r + 1][c] - num),
                    r * n + c,
                    (r + 1) * n + c,
                })
            }
        }
    }
    sort.Slice(edges, func(i, j int) bool {
        return edges[i][0] <= edges[j][0]
    })
    unionFind := newConstruct(m * n)
    for _, edge := range edges {
        unionFind.union(edge[1], edge[2])
        if unionFind.find(0) == unionFind.find(m * n - 1) {
            return edge[0]
        }
    }
    return 0
}

type UnionFind struct {

    parents []int

}

func newConstruct(n int) *UnionFind {
    parents := make([]int, n)
    for i := 0; i < n; i++ {
        parents[i] = i
    }
    return &UnionFind{
        parents: parents,
    }
}

func (this *UnionFind) union(num1, num2 int) {
    parents := this.parents
    target1 := this.find(num1)
    target2 := this.find(num2)
    if target1 == target2 {
        return
    }
    parents[target1] = target2
}

func (this *UnionFind) find(num int) int {
    parents := this.parents
    if parents[num] == num {
        return num
    }
    return this.find(parents[num])
}

func abs(num int) int {
    if num >= 0 {
        return num
    }
    return -num
}