Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- we are using the grid as the visited array and when we push any point in queue,make it visted or in grid 0
- '''
- from typing import List
- from collections import deque
- def is_feasible(a,b,grid):
- if a>=0 and b>=0 and a<len(grid) and b<len(grid[0]) and grid[a][b]==1:
- return True
- return False
- class Solution:
- def shortestPath(self,grid:List[List[int]],src: List[int], dest: List[int]) -> int:
- a,b=src[0],src[1]
- y,z=dest[0],dest[1]
- if grid[a][b]==0:
- return -1
- if src==dest:
- return 0
- q=deque()
- q.append([a,b,0])
- # mark source as visited directly in grid
- grid[a][b] = 0
- while len(q)>0:
- k=len(q)
- for i in range(k):
- a,b,dist=q.popleft()
- x_cord=[-1,0,1,0]
- y_cord=[0,1,0,-1]
- for k in range(4):
- new_a=a+x_cord[k]
- new_b=b+y_cord[k]
- if new_a==y and new_b==z:
- return dist+1
- if is_feasible(new_a,new_b,grid):
- q.append([new_a,new_b,dist+1])
- # mark visited in grid
- grid[new_a][new_b]=0
- return -1
Advertisement
Add Comment
Please, Sign In to add comment