给定一个二维数组，其中全是非负数，
每一步都可以往上、下、左、右四个方向运动。
返回从左上角走到右下角的最短距离。
单元最短路径算法。堆。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
arr := [][]int{
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}}
ret := bestWalk2(arr)
fmt.Println(ret)
}
func bestWalk2(map0 [][]int) int {
n := len(map0)
m := len(map0[0])
// 堆
// 每一个对象，都是一个小数组
// {dis, row, col}
// 0 1 2
heap0 := make([][]int, 0)
// X,0,1 已经弹出了！ 以后在遇到(0,1)的事情，不管！
// poped记录哪些位置弹出，哪些没有！
poped := make([][]bool, n)
for i := 0; i < n; i++ {
poped[i] = make([]bool, m)
}
heap0 = append(heap0, []int{map0[0][0], 0, 0})
ans := 0
for len(heap0) > 0 {
sort.Slice(heap0, func(i, j int) bool {
a := heap0[i]
b := heap0[j]
return a[0] < b[0]
})
cur := heap0[0]
heap0 = heap0[1:]
dis := cur[0]
row := cur[1]
col := cur[2]
if poped[row][col] {
continue
}
// 接下来就是要处理这个位置了！
poped[row][col] = true
if row == n-1 && col == m-1 {
ans = dis
break
}
add(dis, row-1, col, n, m, map0, poped, &heap0)
add(dis, row+1, col, n, m, map0, poped, &heap0)
add(dis, row, col-1, n, m, map0, poped, &heap0)
add(dis, row, col+1, n, m, map0, poped, &heap0)
}
return ans
}
func add(pre, row, col, n, m int, map0 [][]int, used [][]bool, heap0 *[][]int) {
if row >= 0 && row < n && col >= 0 && col < m && !used[row][col] {
*heap0 = append(*heap0, []int{pre + map0[row][col], row, col})
}
}执行结果如下：
