1293. Shortest Path in a Grid with Obstacles Elimination¶
题目信息¶
- 题号:
1293
- 难度:
Hard
- 主题:
网格、广度优先搜索、状态扩展、障碍消除
- 原题:
- 重点:
从左上角四向移动到右下角,最多消除
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
解释:起点的两个可移动方向都是障碍,无法执行第一步。