Maze with BFS
user_0443324754
python
3 years ago
2.2 kB
54
Indexable
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)
Editor is loading...