leetcode 网络中最短的路

网格中的最短路径

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。

如果您最多可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

广度法

def f(grid,k):
    m,n = len(grid), len(grid[0])
    seen = set({(0,0,k)})
    queue = collections.deque([(0,0,k)])
    k = min(k, m + n-3)
    step = 0
    while queue:
        size = len(queue)
        for _ in range(size):
            x,y,k = queue.popleft()
            if x == m - 1 and y == n - 1:
                return step
            for nx,ny in [(0,1), (0,-1), (1,0), (-1,0)]:
                x1 = x + nx
                y1 = y + ny
                item = (x1, y1, k)
                if 0 <= x1 < m and 0 <= y1 < n:
                    if grid[x1][y1] == 0:
                        if item not in seen:
                            queue.append((x1, y1, k))
                            seen.add(item)
                    else:
                        if k > 0:
                            if item not in seen:
                                queue.append((x1, y1, k-1))
                                seen.add(item)
        step += 1


    return -1