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
| from collections import deque
def solution(maps):
n = len(maps)
m = len(maps[0])
visited = [[False for col in range(len(maps[0]))] for row in range(len(maps))]
visited[0][0] = True
queue = deque()
queue.append((0,0,1))
while queue:
yIndex, xIndex, distance = queue.popleft()
if xIndex == n-1 and yIndex == m-1:
return distance
if 0<xIndex+1<n and visited[yIndex][xIndex+1] == False and maps[yIndex][xIndex+1] == 1:
queue.append((yIndex, xIndex+1, distance+1))
visited[yIndex][xIndex+1] = True
if 0<yIndex+1<m and visited[yIndex+1][xIndex] == False and maps[yIndex+1][xIndex] == 1:
queue.append((yIndex+1, xIndex, distance+1))
visited[yIndex+1][xIndex] = True
if 0<xIndex-1<n and visited[yIndex][xIndex-1] == False and maps[yIndex][xIndex-1] == 1:
queue.append((yIndex, xIndex-1, distance+1))
visited[yIndex][xIndex-1] = True
if 0<yIndex-1<m and visited[yIndex-1][xIndex] == False and maps[yIndex-1][xIndex] == 1:
queue.append((yIndex-1, xIndex, distance+1))
visited[yIndex-1][xIndex] = True
return -1
|