Shortest Distance in a Binary Maze

Find the absolute shortest path from a given source cell to a destination cell in an $N \times M$ binary matrix (maze), where valid moves can only traverse cells containing 1s, and each step incurs a uniform cost of 1.

1. Problem Statement & Status Quo

The Scenario

You are given an $N \times M$ matrix where every cell contains either a 0 (blocked wall/obstacle) or a 1 (open path).

• Source Coordinate: Starting position (sr, sc).
• Destination Coordinate: Target position (dr, dc).
• Movement Rules: You can move strictly in 4 directions (Up, Right, Down, Left). Diagonal movements are not permitted.
• Step Cost: Moving from any valid cell to an adjacent valid cell costs exactly 1 unit of distance.
• Objective: Return the minimum steps required to reach the destination. If no valid path exists, return -1.

Real-Life Analogy: Navigating a City Grid

Note: Imagine trying to walk from your apartment to a coffee shop through city blocks. Every street block walked takes exactly 1 minute. Blocked alleys are marked with 0, and open streets are marked with 1. You want to find the absolute fastest route (fewest minutes) without hitting any construction zones. Because every adjacent step takes the exact same amount of time ($1$ unit), uniform-cost traversal is required.

2. Core Mental Model: Why Standard Dijkstra Needs Optimization

Dijkstra's Algorithm Recap

When we hear "shortest path," our immediate reflex is Dijkstra’s Algorithm, which traditionally utilizes a Priority Queue (Min-Heap) and a distance tracking array.

In general graphs (like road networks), edge weights vary widely (e.g., edge weights of $2, 5, 10, 50$). A priority queue is mandatory because nodes are discovered out of order, and we always need to expand the currently known minimum-distance node first to maintain optimality.

The Binary Maze Insight (Constant Unit Weights)

In a binary maze, every single edge weight is identical ($1$).

• If you start at distance $0$, your immediate neighbors will all be reached at distance $1$.
• The neighbors of those neighbors will all be reached at distance $2$.
• The queue naturally maintains an strictly increasing, FIFO-like order of distances (e.g., all $1$s, then all $2$s, then all $3$s).

Because the queue naturally sorts elements in ascending order of distance by virtue of uniform step increments, we do not need a Priority Queue. A standard FIFO Queue (std::queue in C++, Queue in Java) is completely sufficient and avoids the unnecessary $O(\log N)$ overhead introduced by heap insertions and extractions.

3. Initial Configuration & Data Structures

To implement BFS-based shortest path search for a binary maze, we initialize two main structures:

1. Distance 2D Array (dist):
   • Size: $N \times M$
   • Initialized to infinity (1e9) for all cells except the source cell, which is set to 0.
2. Standard Queue (Q):
   • Stores pairs containing the current distance and the cell coordinates: Q.push({ distance, {row, col} }).

Initial Configuration State:

Grid (1s and 0s):        Distance Array (dist):        Queue:
[0, 1, 0, 0]             [Inf,   0, Inf, Inf]          [ (dist=0, {0,1}) ]
[1, 1, 1, 0]             [Inf, Inf, Inf, Inf]
[0, 0, 1, 1]             [Inf, Inf, Inf, Inf]

4. Traversing 4 Directions: Delta Arrays

Since we do not have a pre-built adjacency list, we dynamically discover adjacent neighbors on the fly by applying directional offsets (Delta Rows and Delta Columns).

Direction Vectors:
Delta Row (dr)    = [ -1,  0,  1,  0 ]   (Up, Right, Down, Left)
Delta Column (dc) = [  0,  1,  0, -1 ]

For any current cell (row, col), its 4 neighbors are generated as:

for (int i = 0; i < 4; i++) {
    int newRow = row + dr[i];
    int newCol = col + dc[i];
}

5. Step-by-Step Flow Walkthrough

Let's trace how the queue processes cells step-by-step:

1. Pop Source: Pop (0, 1) with distance 0 from the queue.
2. Explore Neighbors: Check Up, Right, Down, Left.
   • Up: Out of bounds.
   • Right (0, 2): Valid (1), current distance is Inf. Update dist[0][2] = 0 + 1 = 1. Push (1, {0, 2}) to queue.
   • Down (1, 1): Valid (1), current distance is Inf. Update dist[1][1] = 1. Push (1, {1, 1}) to queue.
   • Left (0, 0): Valid (1), current distance is Inf. Update dist[0][0] = 1. Push (1, {0, 0}) to queue.
3. Process Distance Level 1: Pop elements with distance 1 ({0,2}, {1,1}, {0,0}), expanding outward.
4. Target Reached: The moment a neighbor evaluation lands directly on the destination coordinates (dr, dc), we immediately return the accumulated distance without needing to empty the entire queue.

6. Implementation Code (C++ & Java)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, pair<int, int> source, pair<int, int> destination) {
        // Edge Case: If source is already the destination
        if (source == destination) return 0;

        int n = grid.size();
        int m = grid[0].size();

        // Queue stores: {distance, {row, col}}
        queue<pair<int, pair<int, int>>> q;

        // Distance matrix initialized to infinity (1e9)
        vector<vector<int>> dist(n, vector<int>(m, 1e9));

        int sr = source.first, sc = source.second;
        int dr = destination.first, dc = destination.second;

        // Initialize Source
        dist[sr][sc] = 0;
        q.push({0, {sr, sc}});

        // Delta arrays for 4 directions: Up, Right, Down, Left
        int dRow[] = {-1, 0, 1, 0};
        int dCol[] = {0, 1, 0, -1};

        while (!q.empty()) {
            auto it = q.front();
            q.pop();

            int dis = it.first;
            int r = it.second.first;
            int c = it.second.second;

            // Traverse all 4 adjacent neighbors
            for (int i = 0; i < 4; i++) {
                int newR = r + dRow[i];
                int newC = c + dCol[i];

                // Check boundary validity, whether it's a passable cell (1), and if we found a shorter path
                if (newR >= 0 && newR < n && newC >= 0 && newC < m && 
                    grid[newR][newC] == 1 && dis + 1 < dist[newR][newC]) {
                    
                    dist[newR][newC] = dis + 1;

                    // If we reached the destination, return the distance immediately
                    if (newR == dr && newC == dc) {
                        return dis + 1;
                    }

                    q.push({dis + 1, {newR, newC}});
                }
            }
        }

        // If destination is unreachable
        return -1;
    }
};

Java Implementation

import java.util.*;

class Tuple {
    int distance;
    int row;
    int col;

    public Tuple(int distance, int row, int col) {
        this.distance = distance;
        this.row = row;
        this.col = col;
    }
}

class Solution {
    public int shortestPath(int[][] grid, int[] source, int[] destination) {
        // Edge Case: If source equals destination
        if (source[0] == destination[0] && source[1] == destination[1]) {
            return 0;
        }

        int n = grid.length;
        int m = grid[0].length;

        Queue<Tuple> q = new LinkedList<>();
        int[][] dist = new int[n][m];

        // Initialize distances to infinity
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], (int) (1e9));
        }

        int sr = source[0], sc = source[1];
        int dr = destination[0], dc = destination[1];

        dist[sr][sc] = 0;
        q.add(new Tuple(0, sr, sc));

        int[] dRow = {-1, 0, 1, 0};
        int[] dCol = {0, 1, 0, -1};

        while (!q.isEmpty()) {
            Tuple current = q.poll();
            int dis = current.distance;
            int r = current.row;
            int c = current.col;

            for (int i = 0; i < 4; i++) {
                int newR = r + dRow[i];
                int newC = c + dCol[i];

                if (newR >= 0 && newR < n && newC >= 0 && newC < m && 
                    grid[newR][newC] == 1 && dis + 1 < dist[newR][newC]) {
                    
                    dist[newR][newC] = dis + 1;

                    if (newR == dr && newC == dc) {
                        return dis + 1;
                    }

                    q.add(new Tuple(dis + 1, newR, newC));
                }
            }
        }

        return -1;
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Problem Classification: Shortest path finding in unweighted grid graphs maps directly to Breadth-First Search (BFS) principles.
• Why Standard Dijkstra's Priority Queue is Skipped: Because all edge weights (step movements) are uniform ($1$), a standard FIFO queue inherently processes distances in strict ascending order, saving $O(\log N)$ heap overhead.
• Matrix Neighborhood Navigation: Use Delta Arrays (dRow = {-1, 0, 1, 0}, dCol = {0, 1, 0, -1}) to cleanly iterate through all 4 orthogonal directions without writing repetitive conditional blocks.
• Boundary & Obstacle Validation: Always verify that newR and newC reside within grid boundaries and that grid[newR][newC] == 1 before evaluating distances.
• Early Exit Optimization: Terminate and return the calculated distance immediately upon discovering the destination coordinates during neighbor expansion.
• Failure Handling: If the queue empties completely without intersecting the destination cell, return -1 to denote that no valid path exists.