Problem Statement

Given an n*m matrix grid where each cell contains either 0 or 1, determine the shortest distance between a source cell and a destination cell. You can move to an adjacent cell (up, down, left, or right) if the adjacent cell has a value of 1. The path can only be created out if cells containing 1. If the destination cell is not reachable from the source cell, return -1.

Examples

Example 1:

Input: grid = [
               [1, 1, 1, 1],
               [1, 1, 0, 1],
               [1, 1, 1, 1],
               [1, 1, 0, 0],
               [1, 0, 0, 1]
              ]
        source = [0, 1]
        destination = [2, 2]

Output: 3

Explanation: The shortest path from (0, 1) to (2, 2) is:
Move down to (1, 1)
Move down to (2, 1)
Move right to (2, 2)
Thus, the shortest distance is 3.

 Example 2:
 
 Input: grid = [
                [1, 1, 1, 1, 1],
                [1, 1, 1, 1, 1],
                [1, 1, 1, 1, 0],
                [1, 0, 1, 0, 1]
               ]
        source = [0, 0]
        destination = [3, 4]
Output: -1

Explanation: Since, there is no path possible between the source cell and the destination cell, hence wer return -1.

Different Approaches

1️⃣ BFS

Intuition:

The problem includes finding the shortest path from the source to destination which gives the idea of using a Dijsktra's Algorithm. But since, all the edges are of unit weight, instead of using Dijsktra's algorithm, a simple BFS traversal will get the job done.

This involves using the Queue data structure in place of the Min-heap data structure improving the time complexity. As BFS traversal visits all cells in a level order fashion, it will ensure that whenever the destination cell is reached, it is reached via the shortest path.

A distance array will be used to store the shortest path of the intermediate nodes from the source node which will also be used to identify if a shorter path is found leading to the destination cell.

How to traverse the neighbors efficiently?

The 4 neighbors of the current cell can be shown like this:

For efficient traversal of all neighboring pixels, the delRow and delCol arrays can be used where:

• delRow = {-1, 0, 1, 0}
• delCol = {0, 1, 0, -1}

Edge Cases:

• If the source and destination cell are identical, 0 can be returned as the answer.
• If no path from the source node to the destination node is found, -1 can be returned as the answer.

Approach:

1. Create a queue to facilitate BFS traversal. Each element in the queue stores the distance from the source and the coordinates of the cell. Determine the dimensions of the grid.
2. Create a distance matrix initialized to infinity to store the shortest distance from the source to each cell. Set the distance of the source cell to 0 and add it to the queue.
3. While the queue is not empty, process each cell:
   1. Dequeue a cell and retrieve its distance and coordinates.
   2. Iterate through its neighbors using the delta row and column arrays.
   3. For each valid neighbor that contains a 1 and offers a shorter path, update the distance matrix.
   4. If the destination cell is reached, return the distance.
4. If the queue is exhausted without reaching the destination, return -1, indicating the destination is not reachable.

Code:

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

class Solution{
private:

    // Delta row and column array
    vector<int> delRow = {-1, 0, 1, 0};
    vector<int> delCol = {0, -1, 0, 1};
    
    // Function to check if a cell is valid
    bool isValid(int &row, int &col, 
                 int &n, int &m) {
                     
        // Return false if the cell is invalid
        if(row < 0 || row >= n) return false;
        if(col < 0 || col >= m) return false;
        
        // Return true if the cell is valid
        return true;
    }
    
public:

    /* Function to determine the shortest distance
    between source and destination */
    int shortestPath(vector<vector<int>> &grid, pair<int, int> source,
                     pair<int, int> destination) {

        // Edge Case
        if (source.first == destination.first &&
            source.second == destination.second)
            return 0;

        /* Queue data structure to store the pairs of the 
        form: {dist, {coordinates of cell}} */
        queue<pair<int, pair<int, int>>> q;
        
        // Dimensions of grid
        int n = grid.size();
        int m = grid[0].size();

        // Distance matrix
        vector<vector<int>> dist(n, vector<int>(m, 1e9));
        
        // Distane of source from itself is zero
        dist[source.first][source.second] = 0;
        
        // Add the surce to queue
        q.push({0, {source.first, source.second}});

        // Until the queue is empty
        while (!q.empty()) {
            // Get the element
            auto it = q.front();
            q.pop();
            
            int dis = it.first; // Distance
            int row = it.second.first; // Row of cell
            int col = it.second.second; // Column of cell

            // Iterate through all the neighbors
            for (int i = 0; i < 4; i++){
                
                // Coordinates of the new cell
                int newRow = row + delRow[i];
                int newCol = col + delCol[i];

                /* Checking the validity of the cell and 
                updating if a shorter distance is found */
                if (isValid(newRow, newCol, n, m) && 
                    grid[newRow][newCol] == 1 && 
                    dis + 1 < dist[newRow][newCol]) {
                    
                    // Update the distance
                    dist[newRow][newCol] = 1 + dis;

                    // Return the distance is the destination is reached
                    if (newRow == destination.first &&
                        newCol == destination.second)
                        return dis + 1;
                    
                    // Add the new cell to queue
                    q.push({1 + dis, {newRow, newCol}});
                }
            }
        }
        
        // If no path is found from source to destination
        return -1;
    }
};

int main() {
    pair<int, int> source, destination;
    source.first = 0;
    source.second = 1;
    destination.first = 2;
    destination.second = 2;
    
    vector<vector<int>> grid = {
        {1, 1, 1, 1},
        {1, 1, 0, 1},
        {1, 1, 1, 1},
        {1, 1, 0, 0},
        {1, 0, 0, 1} 
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to determine the shortest 
    distance between source and destination */
    int ans = sol.shortestPath(grid, source, destination);
    
    cout << "The shortest distance from the source to destination is: " << ans;
    
    return 0;
}

Complexity Analysis

• Time Complexity:
  • Grid Traversal:
    • In the worst-case scenario, every cell in the grid is visited exactly once.
      • There are n*m cells.
  • Neighbor Checks:
    • For each cell, the algorithm checks at most 4 neighbors (up, down, right, left). Since this is a constant factor (4). It does not change the overall time complexity.
  • Overall:
    • The worst-case time complexity is therefore O(n*m).
• Space Complexity:
  • Visited Matrix:
    • A n*m boolean matrix is used to keep track of visited calls, which requires O(n*m) space.
  • Queue:
    • In the worst-case (for example, when the grid is one large connected component), the queue could store a significant portion of the cells up to O(n*m) in the worst-case.
  • Overall:
    • The space complexity is also O(n*m).