2021-11-21:map[i][j] == 0,代表(i,j)是海洋,渡过的话代价
2023-03-15 22:07:28 时间
2021-11-21:mapi == 0,代表(i,j)是海洋,渡过的话代价是2,
mapi == 1,代表(i,j)是陆地,渡过的话代价是1,
mapi == 2,代表(i,j)是障碍,无法渡过,
每一步上、下、左、右都能走,返回从左上角走到右下角最小代价是多少,如果无法到达返回-1。
来自网易。
答案2021-11-21:
A*算法。根据代价排小根堆,到最后就是最优解。小根堆空了,返回-1。
时间复杂度:O((N*2)logN)。
额外空间复杂度:O(N**2)。
代码用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
}
}
执行结果如下:
相关文章
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- 太快太不安全:为Mongo Express Web管理界面保驾护航
- 怎样在Kubernetes上运行PostgreSQL
- NoSQL中负载均衡系统如何解决热点问题,提高可用性?
- 服务器部署前端&Node 项目(包括阿里云服务器、nginx 以及 mongoDB 的配置)
- 日均5亿查询量的京东到家订单中心,为什么舍MySQL用ES?
- 如何在MySQL 8中重置root密码
- 浅谈SQL Server内部运行机制
- MySQL8.0里GROUP BY有变化,注意了
- 删库跑路?这篇文章教你如何使用xtraback备份MySQL数据库
- 你的数据仓库还在为企业业务拖后腿吗?
- Linux服务器Redis漏洞被利用挖矿解决方法
- 使用Kafka和MongoDB进行Go异步处理
- 收藏备用,MySQL 8下忘密码后重置密码的办法(MySQL5老方法不灵了)
- 数据库不适合Docker及容器化的7大原因
- MariaDB 10.3首推系统版本表,误删数据不用跑路了!
- 七年一剑 华丽蜕变:WOT2018揭秘技术背后的真相
- 区块链真相如何?这篇文章说透了!
- 利用DB实现分布式锁的思路
- 区块链技术如果融合到各个行业,将如何改变我们的生活?