1293. Shortest Path in a Grid with Obstacles Elimination

题目信息

题号:

1293

难度:

Hard

主题:

网格、广度优先搜索、状态扩展、障碍消除

原题:

LeetCode 1293

重点:

从左上角四向移动到右下角,最多消除 k 个值为 1 的障碍;返回最少步数,不可达返回 -1

题目重述

给定 m x n 二进制矩阵 grid,0 表示空格,1 表示障碍。起点为左上角,终点为右下角,每一步只能移动到上下左右相邻格。

最多可以消除 k 个障碍并进入对应格子。请返回到达终点所需的最少移动步数;若即使使用允许的消除次数也无法到达,返回 -1。

1 <= m, n <= 40,1 <= m * n,0 <= k <= m * n,起点和终点均为空格。

自建示例

无需消除障碍时沿空路绕行:

输入:grid = [[0,1,0],[0,1,0],[0,0,0]], k = 0
输出:4
解释:沿左列向下,再沿最后一行向右,共移动四步。

障碍完全切断路径且不能消除:

输入:grid = [[0,1],[1,0]], k = 0
输出:-1
解释:起点的两个可移动方向都是障碍,无法执行第一步。