1368. Minimum Cost to Make at Least One Valid Path in a Grid¶
题目信息¶
- 题号:
1368
- 难度:
Hard
- 主题:
网格、最短路径、0-1 广度优先搜索
- 原题:
- 重点:
每格箭头
1/2/3/4分别指向右、左、下、上;沿原箭头移动成本零,修改该格箭头成本一
题目重述¶
给定整数网格 grid,每个格子包含一个方向箭头。路径从左上角开始,每次按照当前格子的箭头移动到相邻格;指向网格外的箭头不能形成有效下一步。
可以修改任意格子的箭头方向,每个被修改格子成本为 1。请返回使至少存在一条从左上角到右下角有效路径的最小总成本。
1 <= grid.length, grid[i].length <= 100,每个值为 1 到 4。
自建示例¶
只需修改一个转向位置:
输入:grid = [[1,1],[4,3]]
输出:1
解释:先免费向右到达 (0,1),把该格箭头改为向下即可到达终点。
原箭头已经形成有效路径:
输入:grid = [[1,3],[4,1]]
输出:0
解释:路径按右、下两步直接到达右下角。