# Shortest Path to the Destination

BFS

## # Input & Output

@param targetMap: [[int]]
@return: nothing

1
2

## # Solution

### # BFS

Note:

1. constants are separately stored
2. var DIRECTIONS moves x or y by $1$
3. method is_valid checks if a position (x,y) is valid

Complexity

time: $O(mn)$ ($O(V+E)$ for BFS)
space: $O(mn)$

WALL = 1
DESTINATION = 2
DIRECTIONS = [[0,-1], [0,1], [-1,0], [1,0]]
def shortestPath(self, targetMap):
if not targetMap or not targetMap[0]:
return -1

# initialize queue and visited set
queue = []
queue.append((0,0))
visited = set()
step = 0

while queue:
n = len(queue)
for _ in range(n):
x,y = queue.pop(0)
if targetMap[x][y]==DESTINATION:
return step

for direction in DIRECTIONS:
next_x = direction[0] + x
next_y = direction[1] + y
if self.is_valid(next_x, next_y, targetMap, visited):
queue.append((next_x, next_y))
step += 1
return -1

def is_valid(self, x, y, targetMap, visited):
if not 0 <= x < len(targetMap) or not 0 <= y < len(targetMap[0]):
return False
return targetMap[x][y]!=WALL and (x,y) not in visited

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34