2022-04-10：给定一个二维数组，其中全是非负数， 每一步都可以往上、下、左、右四个方向运动

2022-04-10：给定一个二维数组，其中全是非负数， 每一步都可以往上、下、左、右四个方向运动。 返回从左上角走到右下角的最短距离。

答案2022-04-10：

单元最短路径算法。堆。

代码用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})
	}
}

执行结果如下：

左神java代码