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代码
