codejump
MediumPro challengePythonJavaScriptTypeScript

Graph — Shortest Path in a Binary Matrix

Data StructuresGraphsBFSMatrix

solve(grid) — grid is an n × n matrix of 0 (open) and 1 (blocked). Find
the shortest path from the top-left cell to the bottom-right cell, moving through
open cells in 8 directions (diagonals allowed). Return the number of cells on
the path, or -1 if there is none.

Unweighted shortest path means BFS; the only twist is the 8 neighbours.

Examples

solve([[0,1],[1,0]])                 → 2     // one diagonal step
solve([[0,0,0],[1,1,0],[1,1,0]])     → 4
solve([[1,0,0],[1,1,0],[1,1,0]])     → -1    // the start is blocked
solve([[0]])                         → 1

Sample tests

Test #1A single diagonal step
Input: [[[0,1],[1,0]]]
Output: 2
Test #2Around a wall
Input: [[[0,0,0],[1,1,0],[1,1,0]]]
Output: 4
Test #3Blocked start
Input: [[[1,0,0],[1,1,0],[1,1,0]]]
Output: -1
← All challenges