Corn Maze Shortcut
A farm cuts a maze into its corn field every autumn. The owner has the map as rows of characters: # is corn you cannot walk through, . is a path, S is the entrance and E is the exit. Visitors move one square at a time, up, down, left or right.
The owner wants to print the length of the fastest route on the ticket, so visitors know what to beat. Some years a careless cut leaves the exit sealed off, and the ticket should say so.
Your task
Write shortestWalk(maze). maze is a list of equal-length strings. Return the smallest number of steps to get from S to E, where each step moves to a neighboring square up, down, left or right that is not #.
Return -1 if there is no way to reach E. You cannot step outside the map.
shortestWalk(maze: string[]) → int
Examples
maze = ["S.#.", "..#E", "#...", "...."]
6
The wall in column 2 blocks the top two rows. One fastest route: down to (1,0), right to (1,1), down to (2,1), right to (2,2) and (2,3), then up to E at (1,3). That is 6 steps, and no route is shorter because you must go around the wall.
maze = ["S#E"]
-1
The only square between S and E is corn, and there is nowhere else to go. Return -1.
Constraints
- 1 ≤ rows, cols ≤ 20
- Each character is '#', '.', 'S' or 'E'
- There is exactly one 'S' and exactly one 'E'
Start with brute force
Try every route with a depth-first search: walk from S, try each direction, back up at dead ends, and keep the shortest route that reaches E. Do not just return the first route found: depth-first search finds a route, often a long winding one.
Trying every route is hopeless on an open 20 × 20 field. The number of different simple paths across it is astronomically large, even though there are only 400 squares. Most of that work re-walks squares you could already reach faster.
Hints
0 of 4 shown- Hint 1
Take a pencil and the first example. Write 0 on S. Now write 1 on every square you can reach in one step. Then 2 on every new square you can reach from a 1. What do you notice when you reach E?
- Hint 2
Those numbers spread out in rings, like ripples. A square gets the smallest number of steps the first time a ring touches it, and it never needs a different number later.
- Hint 3
Which data structure lets you finish all the squares at distance 1 before you start on distance 2? A stack does not; something else does.
- Hint 4
Run a breadth-first search from S with a queue. Store each square's step count when you first add it, and mark it visited at that moment. Skip walls, squares off the map and visited squares. The first time you take E out of (or put E into) the queue, its count is the answer. If the queue empties first, return -1.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
When every step costs the same, breadth-first search finds shortest routes for free. It handles all squares at distance 1, then all at distance 2, and so on, so the first time it reaches a square is along a shortest route.
Trace the first example. The map is S.#. / ..#E / #... / ...., with S at (0,0) and E at (1,3).
- Distance 0: (0,0).
- Distance 1: (1,0) and (0,1). Their other neighbors are walls, the map edge, or each other.
- Distance 2: (1,1). The square below (1,0) is
#. - Distance 3: (2,1).
- Distance 4: (2,2) and (3,1).
- Distance 5: (2,3), (3,2) and (3,0).
- Distance 6: (1,3), which is E, reached from (2,3). Return 6.
Mark a square visited when you add it to the queue, not when you take it out. Otherwise the same square can be added several times by different neighbors, which wastes work and, on open fields, blows up the queue.
function shortestWalk(maze) {
const rows = maze.length, cols = maze[0].length;
let start = null;
for (let r = 0; r < rows; r++) {
const c = maze[r].indexOf('S');
if (c !== -1) start = [r, c];
}
const dist = maze.map(row => new Array(cols).fill(-1));
dist[start[0]][start[1]] = 0;
const queue = [start];
for (let head = 0; head < queue.length; head++) {
const [r, c] = queue[head];
if (maze[r][c] === 'E') return dist[r][c];
for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (maze[nr][nc] === '#' || dist[nr][nc] !== -1) continue;
dist[nr][nc] = dist[r][c] + 1; // first visit is the shortest
queue.push([nr, nc]);
}
}
return -1; // queue ran out before reaching E
}from collections import deque
def shortest_walk(maze):
rows, cols = len(maze), len(maze[0])
start = None
for r in range(rows):
c = maze[r].find('S')
if c != -1:
start = (r, c)
dist = [[-1] * cols for _ in range(rows)]
dist[start[0]][start[1]] = 0
queue = deque([start])
while queue:
r, c = queue.popleft()
if maze[r][c] == 'E':
return dist[r][c]
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] != '#' and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1 # first visit is the shortest
queue.append((nr, nc))
return -1 # queue ran out before reaching ERun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.