# Maze with BFS

user_0443324754
python
2 years ago
2.2 kB
51
Indexable
Never
```from collections import deque
from sys import maxsize

class Point:
def __init__(self,x=0,y=0):
self.x = x
self.y = y

def bfs(maze, start, end):
#using bfs to find the shortest path.
n, m = len(maze), len(maze[0])
dist = [[maxsize for _ in range(m)] for _ in range(m)]

dxy = [(0,1), (0,-1), (1,0), (-1,0)]
sx, sy = start.x, start.y
ex, ey = end.x, end.y
dist[sx][sy] = 0
q = deque()
q.append(start)
#retrieve the path.
while q:
current = q.popleft()
find = False
for i in dxy:                                   #try out each direction.
dx, dy = i
nx, ny = current.x + dx, current.y + dy
if nx >= 0 and ny >= 0:
#the next step available and never had been.
if nx<n and ny<m and maze[nx][ny] != '#' and dist[nx][ny] == maxsize:

#moving on one step.
dist[nx][ny] = dist[current.x][current.y]+1

#considering as new location.
q.append(Point(nx,ny))
if nx == ex and ny == ey: #found the answer.
find = True
break
if find: break                                  #don't need to try anymore.

#until q was cleared but still no answer.
if dist[ex][ey] == maxsize:
print("IMPOSSIBLE")
else:
print(dist[ex][ey])

if __name__ == '__main__':
n, m = map(int,input().split())
maze = [['' for _ in range(m)] for _ in range(n)]
start = Point()
end = Point()
for i in range(n):
s = input()
maze[i] = list(s)
if 'A' in s:
start.x = i
start.y = s.index('A')
if 'B' in s:
end.x = i
end.y = s.index('B')
bfs(maze, start, end)```