Maze with BFS

 avatar
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)