Iam_Sandeep

Untitled

May 16th, 2026
44
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.94 KB | None | 0 0
  1. from collections import deque
  2.  
  3. def getMinimumMoves(maze, k):
  4.     R = len(maze)
  5.     C = len(maze[0])
  6.    
  7.     tr, tc = R - 1, C - 1
  8.    
  9.     # Base cases
  10.     if maze[0][0] == 1 or maze[tr][tc] == 1:
  11.         return -1
  12.     if tr == 0 and tc == 0:
  13.         return 0
  14.  
  15.     Q = deque([(0, 0, 0)]) # (row, col, moves)
  16.    
  17.     # Track the absolute minimum moves to reach any cell
  18.     dist = [[float('inf')] * C for _ in range(R)]
  19.     dist[0][0] = 0
  20.    
  21.     # 3D DP Array: visited_ray[row][col][direction_index]
  22.     # Tracks the minimum moves to sweep through a cell in a specific direction.
  23.     visited_ray = [[[float('inf')] * 4 for _ in range(C)] for _ in range(R)]
  24.    
  25.     # (dr, dc) pairs mapped to indices 0, 1, 2, 3
  26.     directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
  27.    
  28.     while Q:
  29.         r, c, moves = Q.popleft()
  30.         nd = moves + 1 # Next distance
  31.        
  32.         for d_idx in range(4):
  33.             dr, dc = directions[d_idx]
  34.             nr, nc = r + dr, c + dc
  35.             steps = 1
  36.            
  37.             while steps <= k and 0 <= nr < R and 0 <= nc < C and maze[nr][nc] == 0:
  38.                
  39.                 # 1. 3D DP PRUNING:
  40.                 # If a ray moving in THIS exact direction already swept this cell
  41.                 # in fewer or equal moves, we can mathematically guarantee we can stop.
  42.                 if visited_ray[nr][nc][d_idx] <= nd:
  43.                     break
  44.                    
  45.                 visited_ray[nr][nc][d_idx] = nd
  46.                
  47.                 # 2. Update global shortest path
  48.                 if dist[nr][nc] > nd:
  49.                     if nr == tr and nc == tc:
  50.                         return nd
  51.                        
  52.                     dist[nr][nc] = nd
  53.                     Q.append((nr, nc, nd))
  54.                    
  55.                 # Continue raycasting
  56.                 nr += dr
  57.                 nc += dc
  58.                 steps += 1
  59.                    
  60.     return -1
  61.  
Advertisement
Add Comment
Please, Sign In to add comment