Hard graphs · bfs · grids

Way out of the maze

Drop a ripple at the entrance and let it find the shortest way out.

Write shortestPath(grid): grid is rows of 0 (open) and 1 (wall). Start at the top left, finish at the bottom right, moving up, down, left or right one cell at a time. Return the fewest moves it takes, or -1 if there is no way through (including when the start or finish is a wall, or the grid is empty).

Use breadth-first search. In a copy of the grid, mark visited cells 2 and call show(copy) once per wave of the frontier. When you reach the exit, mark the path you took as 3 and show it. The stage draws empty, wall, visited and path in four colours.

Example: shortestPath([[0, 0, 0], [1, 1, 0], [0, 0, 0]]) returns 4.

Tests you can see

shortestPath([[0,0,0],[1,1,0],[0,0,0]])4
shortestPath([[0,1],[1,0]])-1
shortestPath([[0,0,0],[0,0,0],[0,0,0]])4

More tests are hidden. The server runs them all before a time counts.

Call show() while your code works and the run plays back here.

javascriptshortestPath()

function shortestPath(grid) {
  // a queue (or one frontier array per step), a visited mark, and a step counter
  return -1;
}

function shortestPath(grid) {
  // a queue (or one frontier array per step), a visited mark, and a step counter
  return -1;
}

Tab indents · Cmd/Ctrl+Enter runs