All problems

Shortest Path in Binary Matrix

Medium · graph traversal

A square floor plan is given as an n x n grid of numbers. A 0 is an open tile you can stand on, and a 1 is a blocked tile.

You start on the top-left tile and want to reach the bottom-right tile. From a tile you may step to any of the (up to) eight tiles around it: up, down, left, right and the four diagonals. Every tile you step on, including the first and the last, must be open.

The length of a route is the number of tiles on it, counting both the start and the end. Return the length of the shortest route. If there is no route (this includes the case where the start or the end tile is blocked), return -1. In a 1 x 1 grid whose only tile is open, the answer is 1.

Examples

Example 1

Input: grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]

Output: 4

Go along the top row and then down the right column: 4 tiles in total.

Example 2

Input: grid = [[0, 1], [1, 0]]

Output: 2

The two open tiles touch diagonally, so the route is just those 2 tiles.

Example 3

Input: grid = [[0, 0], [1, 1]]

Output: -1

The bottom-right tile is blocked, so no route can end there.

Constraints

• 1 <= n <= 100, where the grid has n rows and n columns.
• Every tile is 0 or 1.