# LeetCode: 1293. 网格中的最短路径¶

## 1、题目描述¶

输入：
grid =
[[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]],
k = 1



输入：
grid =
[[0,1,1],
[1,1,1],
[1,0,0]],
k = 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$

## 2、解题思路¶

• 深度优先DFS

• 如果k大于等于row + col - 2，可以直接水平垂直过去，也是最短路径

• 最长的路径肯定是每个节点结果一遍，也就是row*col-1

• 设置一个三维数组

steps[i][j][k]


class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
row, col = len(grid), len(grid[0])
if k >= row + col - 2:
return row + col - 2
max_steps = row * col
steps = [[[max_steps for _ in range(k + 1)] for _ in range(col)] for _ in range(row)]
surround = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def available(m, n):
return 0 <= m < row and 0 <= n < col

def dfs(x, y, step, barrier):
steps[x][y][barrier] = min(steps[x][y][barrier], step)

if any([steps[x][y][i] < step for i in range(barrier)]):
return
next_barrier = barrier if grid[x][y] == 0 else barrier + 1
if next_barrier > k:
return

for dx, dy in surround:
nx, ny = x + dx, y + dy
if available(nx, ny) and step + 1 < steps[nx][ny][next_barrier]:
dfs(nx, ny, step + 1, next_barrier)

dfs(0, 0, 0, 0)
res = min(steps[row - 1][col - 1])
return res if res < max_steps else -1