shortest_path_in_binary_matrix
1from collections import deque 2 3 4# @leet start 5class Solution: 6 def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int: 7 """ 8 This question asks us to find the shortest path that goes from the top 9 left to the bottom right in a path of all zeroes. 10 11 Since we're finding the shortest path, we should BFS this. 12 So we define all the eight directions (since we can go in eight directions) 13 and also define a visited set so we don't revisit the same square twice. 14 We then check to make sure that we're at the last square, if we are, we 15 return the amount of squares we've visited so far. 16 """ 17 m, n = len(grid), len(grid[0]) 18 dirs = [ 19 (1, 0), 20 (0, 1), 21 (-1, 0), 22 (0, -1), 23 (1, 1), 24 (-1, -1), 25 (-1, 1), 26 (1, -1), 27 ] 28 29 def inbounds(y, x): 30 return 0 <= y < m and 0 <= x < n 31 32 q = deque([(0, 0, 1)]) 33 visited = set() 34 35 while q: 36 y, x, path_len = q.popleft() 37 if (y, x) in visited or not inbounds(y, x) or grid[y][x] != 0: 38 continue 39 visited.add((y, x)) 40 41 if y == m - 1 and x == n - 1: 42 return path_len 43 for dy, dx in dirs: 44 new_y, new_x = dy + y, dx + x 45 q.append((new_y, new_x, path_len + 1)) 46 47 return -1 48 49 50# @leet end 51 52 53def test(): 54 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int: 8 """ 9 This question asks us to find the shortest path that goes from the top 10 left to the bottom right in a path of all zeroes. 11 12 Since we're finding the shortest path, we should BFS this. 13 So we define all the eight directions (since we can go in eight directions) 14 and also define a visited set so we don't revisit the same square twice. 15 We then check to make sure that we're at the last square, if we are, we 16 return the amount of squares we've visited so far. 17 """ 18 m, n = len(grid), len(grid[0]) 19 dirs = [ 20 (1, 0), 21 (0, 1), 22 (-1, 0), 23 (0, -1), 24 (1, 1), 25 (-1, -1), 26 (-1, 1), 27 (1, -1), 28 ] 29 30 def inbounds(y, x): 31 return 0 <= y < m and 0 <= x < n 32 33 q = deque([(0, 0, 1)]) 34 visited = set() 35 36 while q: 37 y, x, path_len = q.popleft() 38 if (y, x) in visited or not inbounds(y, x) or grid[y][x] != 0: 39 continue 40 visited.add((y, x)) 41 42 if y == m - 1 and x == n - 1: 43 return path_len 44 for dy, dx in dirs: 45 new_y, new_x = dy + y, dx + x 46 q.append((new_y, new_x, path_len + 1)) 47 48 return -1
def
shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
7 def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int: 8 """ 9 This question asks us to find the shortest path that goes from the top 10 left to the bottom right in a path of all zeroes. 11 12 Since we're finding the shortest path, we should BFS this. 13 So we define all the eight directions (since we can go in eight directions) 14 and also define a visited set so we don't revisit the same square twice. 15 We then check to make sure that we're at the last square, if we are, we 16 return the amount of squares we've visited so far. 17 """ 18 m, n = len(grid), len(grid[0]) 19 dirs = [ 20 (1, 0), 21 (0, 1), 22 (-1, 0), 23 (0, -1), 24 (1, 1), 25 (-1, -1), 26 (-1, 1), 27 (1, -1), 28 ] 29 30 def inbounds(y, x): 31 return 0 <= y < m and 0 <= x < n 32 33 q = deque([(0, 0, 1)]) 34 visited = set() 35 36 while q: 37 y, x, path_len = q.popleft() 38 if (y, x) in visited or not inbounds(y, x) or grid[y][x] != 0: 39 continue 40 visited.add((y, x)) 41 42 if y == m - 1 and x == n - 1: 43 return path_len 44 for dy, dx in dirs: 45 new_y, new_x = dy + y, dx + x 46 q.append((new_y, new_x, path_len + 1)) 47 48 return -1
This question asks us to find the shortest path that goes from the top left to the bottom right in a path of all zeroes.
Since we're finding the shortest path, we should BFS this. So we define all the eight directions (since we can go in eight directions) and also define a visited set so we don't revisit the same square twice. We then check to make sure that we're at the last square, if we are, we return the amount of squares we've visited so far.
def
test():