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

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 main

import (
    "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  int
    col  int
    cost int
}

func NewNode(a, b, c int) *Node {
    ret := &Node{}
    ret.row = a
    ret.col = b
    ret.cost = c
    return ret
}

func twoSelectOne(c bool, a int, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

执行结果如下：

左神java代码