問題
題目在這。
解題思路
格子題，從左上到右下需要的最小步數。難點在給了個預算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
