1368. Minimum Cost to Make at Least One Valid Path in a Grid

题目信息

题号:

1368

难度:

Hard

主题:

网格、最短路径、0-1 广度优先搜索

原题:

LeetCode 1368

重点:

每格箭头 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
解释:路径按右、下两步直接到达右下角。