Shortest way through the maze

Problem

A maze is a grid. S is the start, E is the exit, . is open floor and # is a wall. You move one step up, down, left or right onto a non-wall cell. Print the fewest steps from S to E, or -1 if the exit cannot be reached.

Input, output and limits

Input: Line 1: rows and columns. Then one line per row. There is exactly one S and one E.
Output: One integer.
Constraints: 1 ≤ rows, columns ≤ 300

Examples

Example 1

Input

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

Output

Example 2

Input

1 3
S#E

Output

-1

Hints

Try the problem first. Open one hint at a time.

Hint 1

Treat each cell as a node and use BFS from S.

Hint 2

Walls are never pushed onto the queue.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Tasks that wait for each othermedium
Largest land patchmedium
Loop in the cablingmedium
Exactly k links awaymedium
Biggest networkmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Graphs: Basics & Traversal problems

Problem

Input, output and limits

Examples

Hints

More Graphs: Basics & Traversal problems