Minimum Path in Binary Grid

MEDIUM25 pts

You are given an n × n grid of binary values where each cell contains either a 0 (representing an open/passable cell) or a 1 (representing a blocked/impassable cell). Your objective is to determine the minimum number of cells you must traverse to travel from the top-left corner (cell at position (0, 0)) to the bottom-right corner (cell at position (n-1, n-1)).

A valid path must satisfy the following conditions:

All cells visited along the path must contain the value 0 — you cannot pass through blocked cells.
Movement is allowed in 8 directions: You can move to any of the 8 neighboring cells that share an edge or a corner with your current cell (up, down, left, right, and all four diagonals).
The path length is measured by counting all cells visited, including both the starting cell and the destination cell.

If no valid path exists from the top-left to the bottom-right corner (for example, if either the start or end cell is blocked, or if blocked cells completely obstruct all possible routes), return -1.

Movement Directions Explained: From any cell (row, col), you can move to the following 8 adjacent cells if they are within bounds and contain a 0:

(row-1, col-1) — top-left diagonal
(row-1, col) — directly above
(row-1, col+1) — top-right diagonal
(row, col-1) — directly left
(row, col+1) — directly right
(row+1, col-1) — bottom-left diagonal
(row+1, col) — directly below
(row+1, col+1) — bottom-right diagonal

Example

Input

grid = [[0,1],[1,0]]

Output

2

Explanation

The only path from (0,0) to (1,1) is a diagonal move. The path visits 2 cells: the start (0,0) and the destination (1,1). Despite the blocked cells at (0,1) and (1,0), we can traverse diagonally since diagonal movement is allowed.

Example

Input

grid = [[0,0,0],[1,1,0],[1,1,0]]

Output

4

Explanation

One valid minimum path is: (0,0) → (0,1) → (0,2) → (1,2) → (2,2). This path visits 4 cells. Moving right along the top row, then down along the right column avoids all blocked cells.

Example

Input

grid = [[1,0,0],[1,1,0],[1,1,0]]

Output

-1

Explanation

The starting cell (0,0) contains a 1 (blocked), so it is impossible to begin any path. Therefore, no valid path exists, and we return -1.

Accepted0/0·0% Acceptance

Constraints

n == grid.length
n == grid[i].length
1 ≤ n ≤ 100
grid[i][j] is either 0 or 1

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

grid =

[[0,1],[1,0]]

Minimum Path in Binary Grid

Hints

Minimum Path in Binary Grid

Hints