Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import deque
- def getMinimumMoves(maze, k):
- R = len(maze)
- C = len(maze[0])
- tr, tc = R - 1, C - 1
- # Base cases
- if maze[0][0] == 1 or maze[tr][tc] == 1:
- return -1
- if tr == 0 and tc == 0:
- return 0
- Q = deque([(0, 0, 0)]) # (row, col, moves)
- # Track the absolute minimum moves to reach any cell
- dist = [[float('inf')] * C for _ in range(R)]
- dist[0][0] = 0
- # 3D DP Array: visited_ray[row][col][direction_index]
- # Tracks the minimum moves to sweep through a cell in a specific direction.
- visited_ray = [[[float('inf')] * 4 for _ in range(C)] for _ in range(R)]
- # (dr, dc) pairs mapped to indices 0, 1, 2, 3
- directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
- while Q:
- r, c, moves = Q.popleft()
- nd = moves + 1 # Next distance
- for d_idx in range(4):
- dr, dc = directions[d_idx]
- nr, nc = r + dr, c + dc
- steps = 1
- while steps <= k and 0 <= nr < R and 0 <= nc < C and maze[nr][nc] == 0:
- # 1. 3D DP PRUNING:
- # If a ray moving in THIS exact direction already swept this cell
- # in fewer or equal moves, we can mathematically guarantee we can stop.
- if visited_ray[nr][nc][d_idx] <= nd:
- break
- visited_ray[nr][nc][d_idx] = nd
- # 2. Update global shortest path
- if dist[nr][nc] > nd:
- if nr == tr and nc == tc:
- return nd
- dist[nr][nc] = nd
- Q.append((nr, nc, nd))
- # Continue raycasting
- nr += dr
- nc += dc
- steps += 1
- return -1
Advertisement
Add Comment
Please, Sign In to add comment