Shortest Path (BFS)

Lab Python Advanced 30 points

Read a grid of . (open) and # (wall) with S start and E end. Print the length of the shortest path moving up/down/left/right, or -1.

Input

Line 1: rows cols. Then the grid rows.

Output

One integer.

Example

Input

3 4
S..#
.#..
...E

Output

Sample input available Sample output available

Editor

Python

Hints

Breadth-first search explores cells in order of distance.

Use a deque as the queue and a dict for distances.

Solution explanation

BFS finds shortest paths in unweighted graphs; grids are graphs where neighbours are adjacent cells.

Show solution

from collections import deque

r, c = map(int, input().split())
grid = [input() for _ in range(r)]
start = next((i, j) for i in range(r) for j in range(c) if grid[i][j] == "S")
dist = {start: 0}
queue = deque([start])
answer = -1
while queue:
    i, j = queue.popleft()
    if grid[i][j] == "E":
        answer = dist[(i, j)]
        break
    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        ni, nj = i + di, j + dj
        if 0 <= ni < r and 0 <= nj < c and grid[ni][nj] != "#" and (ni, nj) not in dist:
            dist[(ni, nj)] = dist[(i, j)] + 1
            queue.append((ni, nj))
print(answer)

Output

Answer