问题
题目在这。
解题思路
格子题，从左上到右下需要的最小步数。难点在给了个预算k，最多可以穿墙k次。找距离需要用BFS，不走回头路就可以，比较简单。但是这题在空间上是有可能走回头路的，因为除了空间以外，还多了个状态是已经穿墙几次。放到queue里面的应该是（坐标，穿墙次数）的tuple。所以关键在于不要把相同（坐标，穿墙次数）放queue里，不然会无法停止。
Python解法
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
rows, cols = len(grid), len(grid[0])
def valid(cord):
return 0 <= cord[0] < rows and 0 <= cord[1] < cols
def nbs(cord):
dirs = [
(0,1),
(0,-1),
(1,0),
(-1,0)
]
new_cords = [ (cord[0] + dir[0], cord[1] + dir[1]) for dir in dirs]
return list(filter(lambda x: valid(x), new_cords))
def seen_to_grid(seen):
grid = [[None for c in range(cols)] for r in range(rows)]
for key in seen:
cord, removed = key
if grid[cord[0]][cord[1]] is None:
grid[cord[0]][cord[1]] = []
grid[cord[0]][cord[1]].append(removed)
print_grid(grid)
def print_grid(grid):
for row in grid:
row_of_str = [str(col) for col in row]
print(' '.join(row_of_str))
print()
q = [((0,0), grid[0][0], 0)]
seen = set()
while q:
cord, removed, dist = q.pop(0)
seen_to_grid(seen)
if removed > k or (cord, removed) in seen:
continue
seen.add((cord, removed))
if cord == (rows-1, cols-1):
return dist
next_cords = nbs(cord)
for next_cord in next_cords:
q.append(
(next_cord,
removed + grid[next_cord[0]][next_cord[1]],
dist+1)
)
return -1
