// dfs确定状态+疯狂剪枝
func shortestPath(grid [][]int, k int) int {
m, n := len(grid), len(grid[0])
if k >= m+n-3 {
return m + n - 2
}
// 三维记忆数组， [x][y][cnt1] 分别表示坐标和当前墙的数量，存储的值为当前状态下遍历过的最短路径长度
// 当坐标和当前墙的数量相等时，继续带入 dfs， 递归的路径是一样的
// 所以如果某状态下，当前路径长度大于等于 vis 记录的路径长度，继续递归，只会得到更大或相等的结果，所以直接返回
vis := make([][][]int, m)
for i := range vis {
vis[i] = make([][]int, n)
for j := range vis[i] {
vis[i][j] = make([]int, k+1)
for l := range vis[i][j] {
vis[i][j][l] = math.MaxInt
}
}
}
var dirs4 = [][2]int{{-1, 0}, {1, 0}, {0, 1}, {0, -1}}
ans := math.MaxInt
var dfs func(int, int, int, int)
dfs = func(x, y, cnt, wallCnt int) {
if grid[x][y] == 1 {
wallCnt++ // 墙数量+1
}
cnt++ // 路径+1
if wallCnt > k { // 多于k个墙 寄
return
}
if cnt >= ans { // 路径数量大于等于之前的答案，最短，就没必要了
return
}
if x == m-1 && y == n-1 { // 到达，更新答案
ans = cnt
return
}
if cnt >= vis[x][y][wallCnt] { // 当前路径长度大于等于记忆化的那个，寄
return
}
vis[x][y][wallCnt] = cnt // 记忆化
for i := 0; i < 4; i++ { // 4偏移量
a, b := x+dirs4[i][0], y+dirs4[i][1]
if a >= 0 && a < m && b >= 0 && b < n {
dfs(a, b, cnt, wallCnt)
}
}
}
dfs(0, 0, -1, 0)
if ans == math.MaxInt { // 寄
return -1
}
return ans
}
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
if not any(grid): return -1
m, n = len(grid), len(grid[0])
k = min(k, m+n-3)
q = [(0, 0, k, 0)]
visited = {(0, 0, k)}
while q:
x, y, rest, steps = q.pop(0)
if x == m-1 and y == n-1:
return steps
for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
if 0 <= nx < m and 0 <= ny < n:
nk = rest-grid[nx][ny]
if nk < 0 or (nx, ny, nk) in visited:
continue
q.append((nx, ny, nk, steps+1))
visited.add((nx, ny, nk))
return -1
# bfs
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
if m == 1 and n == 1:
return 0
k = min(k, m + n - 3)
visited = set([(0, 0, k)])
q = collections.deque([(0, 0, k)])
step = 0
while len(q) > 0:
step += 1
cnt = len(q)
for _ in range(cnt):
x, y, rest = q.popleft()
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, 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
q.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:
q.append((nx, ny, rest - 1))
visited.add((nx, ny, rest - 1))
return -1
