imashutosh51

Shortest distance in binary maze

Jul 31st, 2022 (edited)
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.31 KB | None | 0 0
  1. '''
  2. we are using the grid as the visited array and when we push any point in queue,make it visted or in grid 0
  3. '''
  4. from typing import List
  5. from collections import deque
  6.  
  7. def is_feasible(a,b,grid):
  8.     if a>=0 and b>=0 and a<len(grid) and b<len(grid[0]) and grid[a][b]==1:
  9.         return True
  10.     return False
  11.  
  12. class Solution:
  13.     def shortestPath(self,grid:List[List[int]],src: List[int], dest: List[int]) -> int:
  14.         a,b=src[0],src[1]
  15.         y,z=dest[0],dest[1]
  16.         if grid[a][b]==0:
  17.             return -1
  18.         if src==dest:
  19.             return 0
  20.  
  21.         q=deque()
  22.         q.append([a,b,0])
  23.  
  24.         # mark source as visited directly in grid
  25.         grid[a][b] = 0
  26.        
  27.         while len(q)>0:
  28.             k=len(q)
  29.             for i in range(k):
  30.                 a,b,dist=q.popleft()
  31.                 x_cord=[-1,0,1,0]
  32.                 y_cord=[0,1,0,-1]
  33.                 for k in range(4):
  34.                     new_a=a+x_cord[k]
  35.                     new_b=b+y_cord[k]
  36.                     if new_a==y and new_b==z:
  37.                         return dist+1
  38.                    
  39.                     if is_feasible(new_a,new_b,grid):
  40.                         q.append([new_a,new_b,dist+1])
  41.                         # mark visited in grid
  42.                         grid[new_a][new_b]=0
  43.         return -1
  44.  
Advertisement
Add Comment
Please, Sign In to add comment