BFSのメッシュ内の最短パス

LeetCode 1293. グリッド内の最短パス
m*nのグリッドをあげます.各セルは0(空)ではなく1(障害物)です.各ステップで、空白のセルを上、下、左、右に移動できます.
最大k個の障害物を除去できる場合は、左上隅(0,0)から右下隅(m-1,n-1)までの最短パスを見つけ、パスを通過するために必要なステップ数を返します.このようなパスが見つからない場合は、-1を返します.
例1:

  ： 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
  ：6
  ：
              10。
     (3,2)      ，      6 。
     (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

例2:

  ：
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
  ：-1
  ：
                     。

ヒント:

grid.length == m
grid[0].length == n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] == 0 or 1
grid[0][0] == grid[m-1][n-1] == 0

構想:プレイヤーは最短路で明らかに同じ位置を1回以上通過しないため、最大k個の障害物を除去することは最大k個の障害物を通過することに等しい.

は三元グループ(x,y,rest)を用いて検索状態を表し、(x,y)はプレイヤーの位置を表し、restはプレイヤーがrest個の障害物を通過することもでき、その値は非負の整数でなければならないことを示す.

現在の状態(x,y,rest)については、最大4つの新しい状態を検索することができ、プレイヤー(x,y)が4つの方向に1格移動する.移動方向が(dx,dy)であると仮定すると、プレイヤーの新しい位置は(x+dx,y+dy)である.

この位置が障害物である場合、新しい状態は(x+dx,y+dy,rest−1)であり、そうでない場合、新しい状態は(x+dx,y+dy,rest)である.

初期状態(0,0,k)から探索を開始し,k’が任意の非負の整数であるとき,左上角(0,0)から右下角(m−1,n−1,k’)まで,最大k個の障害物を通過する最短経路を得た.

タイトル中のkの上限はmしたがって,kの値をm+n−3とそれ自体の小さい値min(k, m + n - 3)に設定し,広さ優先探索の時間的複雑さをO(MNK)O(MNK)O(MNK)からO(MN(M+N,K))O(MN*min(M+N,K))O(MN(M+N,K))O(MN(M+N,K))に低減することができる.

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m = len(grid)
        n = len(grid[0])
        if m == 1 and n == 1:
            return 0
        #           ，    0     ，       m+n-2
        if m + n - 3 <= k: 
            return m + n - 2
        k = min(m + n - 3, k)
        visited = set([(0, 0 ,k)])
        queue = [(0, 0, k)]
        
        step = 0
        while len(queue) > 0:
            step += 1
            size = len(queue)
            for _ in range(size):
                x, y, rest = queue.pop(0)
                for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < m and 0 <= ny < n:
                        if grid[nx][ny] == 0 and (nx, ny, rest) not in visited:
                            if nx == m - 1 and ny == n - 1:
                                return step
                            queue.append((nx, ny, rest))
                            visited.add((nx, ny, rest))
                        elif grid[nx][ny] == 1 and rest > 0 and (nx, ny, rest - 1) not in visited:
                            queue.append((nx, ny, rest - 1))
                            visited.add((nx, ny, rest - 1))
        return -1

時間複雑度:O(MN∗min⁡(M＋N,K))O(MN＊min(M＋N,K))))O(MN∗min(M＋N,K)).
空間複雑度:O(MN∗min⁡(M＋N,K))O(MN＊min(M＋N,K))))O(MN∗min(M＋N,K)).