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``,起点和终点均为空格。 自建示例 -------- 无需消除障碍时沿空路绕行: .. code-block:: text 输入:grid = [[0,1,0],[0,1,0],[0,0,0]], k = 0 输出:4 解释:沿左列向下,再沿最后一行向右,共移动四步。 障碍完全切断路径且不能消除: .. code-block:: text 输入:grid = [[0,1],[1,0]], k = 0 输出:-1 解释:起点的两个可移动方向都是障碍,无法执行第一步。