Introduction

Shortest Path in Binary Matrix is one of the most important BFS grid problems.

You are given:

grid[][]

Where:

0 = Empty Cell
1 = Blocked Cell

Goal:

Find shortest path from top-left to bottom-right.

Movement:

8 Directions

Example

Input:

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

Output:

2

Explanation:

(0,0)
↓
(1,1)

Key Observation

All moves have:

Equal Cost

Therefore:

BFS
gives shortest path

Algorithm

1. Check start/end
2. Push source into queue
3. Perform BFS
4. Visit 8 directions
5. Reach destination
6. Return distance

Dry Run

Grid:

0 11 0

Queue:

(0,0)

Next:

(1,1)

Answer:

2

Approach : BFS

Explanation

  1. Start from (0,0).
  2. Visit all 8 directions.
  3. Mark visited cells.
  4. BFS guarantees shortest path.
  5. Return distance when destination is reached.

Practice

Complexity Analysis

Time Complexity: O(n²)
Space Complexity: O(n²)

Why This Problem is Important

  • BFS
  • Grid Traversal
  • Shortest Path
  • Graph Traversal
  • Matrix Problems

Common Beginner Mistakes

  • Using DFS instead of BFS
  • Forgetting diagonal moves
  • Not marking visited cells
  • Wrong boundary checks
  • Missing blocked start/end check

Interview Tip

Always explain:

All edges have equal cost therefore BFS gives shortest path.

Related Questions

  • Number of Islands
  • Rotting Oranges
  • Walls and Gates
  • Network Delay Time

Final Takeaway

Shortest Path in Binary Matrix is a classic BFS shortest path problem.

It teaches:

  • BFS Traversal
  • Grid Graphs
  • Shortest Path Concepts
  • Multi-Directional Movement

Mastering this problem makes advanced graph and matrix traversal questions significantly easier.