2021-11-21：map[i][j] == 0，代表(i,j)是海洋，渡过的话代价是2， map[i][j] == 1，代表(i,j)是陆地，渡过的话代价是1， map[i][j] == 2，代表

2021-11-21：map[i][j] == 0，代表(i,j)是海洋，渡过的话代价是2，
map[i][j] == 1，代表(i,j)是陆地，渡过的话代价是1，
map[i][j] == 2，代表(i,j)是障碍，无法渡过，
每一步上、下、左、右都能走，返回从左上角走到右下角最小代价是多少，如果无法到达返回-1。
来自网易。

答案2021-11-21：

A*算法。根据代价排小根堆，到最后就是最优解。小根堆空了，返回-1。
时间复杂度：O((N2)*logN)。
额外空间复杂度：O(N2)。

代码用golang编写。代码如下：

package mainimport ("fmt""sort"
)func main() {map0 := [][]int{{1, 0, 1},{2, 0, 1},}ret := minCost(map0)fmt.Println(ret)
}func minCost(map0 [][]int) int {if map0[0][0] == 2 {return -1}n := len(map0)m := len(map0[0])heap := make([]*Node, 0) //模拟小根堆visited := make([][]bool, n)for i := 0; i < n; i++ {visited[i] = make([]bool, m)}add(map0, 0, 0, 0, &heap, visited)for len(heap) > 0 {sort.Slice(heap, func(i, j int) bool {a := heap[i]b := heap[j]return a.cost < b.cost})cur := heap[0]heap = heap[1:]if cur.row == n-1 && cur.col == m-1 {return cur.cost}add(map0, cur.row-1, cur.col, cur.cost, &heap, visited)add(map0, cur.row+1, cur.col, cur.cost, &heap, visited)add(map0, cur.row, cur.col-1, cur.cost, &heap, visited)add(map0, cur.row, cur.col+1, cur.cost, &heap, visited)}return -1
}func add(m [][]int, i int, j int, pre int, heap *[]*Node, visited [][]bool) {if i >= 0 && i < len(m) && j >= 0 && j < len(m[0]) && m[i][j] != 2 && !visited[i][j] {*heap = append(*heap, NewNode(i, j, pre+twoSelectOne(m[i][j] == 0, 2, 1)))visited[i][j] = true}
}type Node struct {row  intcol  intcost int
}func NewNode(a, b, c int) *Node {ret := &Node{}ret.row = aret.col = bret.cost = creturn ret
}func twoSelectOne(c bool, a int, b int) int {if c {return a} else {return b}
}

执行结果如下：

左神java代码