Shortest Path in Binary Matrix
Robot across the warehouse. A robot starts on the top-left tile of an n x n floor plan and has to reach the bottom-right tile. grid[r][c] is 0 for a clear tile and 1 for a shelf. In one step it moves onto any of the 8 tiles around it, diagonals included, as long as that tile is clear. A diagonal step is fine even when both tiles beside it are shelves. Return how many tiles the shortest route walks over, counting the start and the goal, or -1 if there is no route. The start or the goal can itself be a shelf, and then there is no route. Limits: 1 <= n <= 700. Heads-up: a route can wind through hundreds of thousands of tiles, so a recursive search can run out of stack (Python stops at 1000 calls by default). A loop with your own queue is the safer choice. Examples: grid = [[0,1,0,0],[1,0,0,0],[0,1,1,0],[1,0,0,0]] => 5 route: (0,0) (1,1) (1,2) (2,3) (3,3) grid = [[0,0],[1,1]] => -1 the goal tile is a shelf
A warehouse robot has to cross a floor plan from the top-left corner to the bottom-right one, stepping onto any clear tile around it, diagonals included, and you want the fewest tiles it walks over. Interviewers love it because it looks like a maze puzzle until you notice that every step costs the same. The classic traps are counting moves instead of tiles and forgetting that the start or the goal can itself be a shelf. Expect floor plans from 1 by 1 up to 700 by 700.
Examples
You write
shortest_path_binary_matrix(grid: List[List[int]])
Example 1
- Input
- grid = [[0,1,0,0],[1,0,0,0],[0,1,1,0],[1,0,0,0]]
- returns
- 5
Example 2
- Input
- grid = [[0]]
- returns
- 1
Save this for your laptop
The editor and Run need a bigger screen. The link opens Shortest Path in Binary Matrix ready to code. It is free, and the editor needs no account.
The pattern behind it
Graphs
I reach for it when
- The input is edges, prerequisites or connections.
- You need cycles, an ordering or connected groups.
Say this before you type. Say whether the edges are directed, and which of the three jobs you are doing.
All 32 Graphs problemsBFS & DFS
I reach for it when
- You walk a grid, a graph or a tree and visit each cell once.
- The word shortest appears and every step costs the same.
Say this before you type. Say why breadth or depth fits, and exactly when a cell counts as visited.
All 52 BFS & DFS problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.