Sky Router

A map arrives as a list of strings. S is the start, E is the end, . is open sky and # is a storm you cannot enter. Each move goes one square up, down, left or right.

Write shortest_route(grid) that returns the fewest moves from S to E, or -1 if no route exists. Use breadth-first search: explore every square one move away, then two, then three. The first time you reach E is guaranteed to be the shortest route.

Build it step by step

Scan the grid to find the row and column of S.
Put (row, col, 0) in a deque and mark it visited.
Pop from the left, and if the square is E return its distance.
Push each open, unvisited neighbour with distance + 1.
If the queue empties without reaching E, return -1.

Examples

shortest_route(['S..', '...', '..E'])

→ 4

shortest_route(['S#.', '.#.', '...', '.#E'])

→ 5

project.py

PYTHON

Saved as you type

Tests

0 of 6 passing

•
open sky
shortest_route(['S..', '...', '..E'])
expected 4
•
storm wall with a gap
shortest_route(['S#.', '.#.', '...', '.#E'])
expected 5
•
no way through
shortest_route(['S#E'])
expected -1
•
neighbours
shortest_route(['SE'])
expected 1
•
switchback
shortest_route(['S....', '####.', 'E....', '.####', '.....'])
expected 10
•
long detour
shortest_route(['S.#...', '#.#.#.', '..#.#.', '.##.#.', '....#E'])
expected 19

On the line

+650 XP

Pass all 6 tests to claim it.