Shortest Path in a Maze (BFS)
Hard · Algorithms
Breadth-first search (BFS) explores a grid in rings: first every cell 1 step away, then every cell 2 steps away, and so on. So the first time BFS reaches the target, it has found the shortest path. Use collections.deque as the queue and a seen set so no cell is visited twice.
The maze is a list of equal-length strings. "S" is the start, "E" is the end, "#" is a wall and "." is open floor. You can move up, down, left or right (no diagonals) and cannot leave the grid.
Write shortest_path(grid) that returns the fewest moves from S to E, or -1 if E cannot be reached. There is exactly one S and one E.