DAY 41 - Shortest Path in a Binary Matrix

Hey everyone! Welcome back to another day of problem-solving. It's day 41, and I'm still going strong on my quest for consistency. Today, we will be doing a continuation of our last problem the change being the graph is weighted now.

Question: Shortest Path in a Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.

Example 1:

• 
• Input: grid = [[0,1],[1,0]]
• Output: 2

Example 2:

• 

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

• Output: 4

Constraints:

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

Intuition:

• Let's start by understanding the question.
• We start from the top left corner of the matrix(0,0) and we have to reach (n-1,n-1)(bottom right corner).
• We are required to do this in the shortest steps taken possible and return the length of sequence.
• We can only move if the cell is 0.
• If we can't reach the end we return -1.
• Hence by observing all these things we will apply Dijkstra's algorithm.

Algorithm:

1. Initial Checks:

We begin by checking the value of the top-left corner of the grid. If it is 1, indicating an obstacle, we return -1 as it is not possible to reach the destination.
Additionally, if the grid has only one cell, which is the source itself, we return 1 as the distance to reach the destination.

2. Initializing Variables:

• We initialize the necessary variables, including the size of the grid (n), the coordinates of the source and destination cells, and a queue to perform a breadth-first search.
• The source is set to (0,0) (top-left corner), and the destination is set to (n-1,n-1) (bottom-right corner).
• We also initialize a 2D array called "dis" to store the minimum distances from the source to each cell. Initially, all distances are set to a large value (1e9), except for the source cell, which is set to 1.
• Lastly, we enqueue the source cell with a distance of 0 to initiate the BFS traversal.

3. Applying Breadth-First Search:

• While the queue is not empty, we dequeue a cell from the front.
• We iterate over the 9 possible adjacent cells (including diagonals) using the "delRow" and "delCol" arrays to determine the row and column changes.
• For each adjacent cell, if it is within the grid boundaries, has a value of 0 (indicating a valid path), and the current distance plus one is smaller than the existing distance stored in "dis," we update the distance accordingly.
• If the current cell is the destination cell, we return 1 plus the distance to reach it, as this is the shortest path.
• Finally, we enqueue the adjacent cell with the updated distance.

4. Returning the Result:

• If we finish traversing the grid without reaching the destination, it means there is no valid path. In this case, we return -1 to indicate the impossibility of reaching the destination.
• However, if we find a valid path and reach the destination, we return 1 plus the distance stored in "dis" at the destination cell, as this represents the shortest path length.

Code:

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid[0][0] != 0){
            return -1;
        }
        if(grid.size() == 1 && grid[0].size() == 1) return 1;
        int n = grid.size();
        pair<int,int> source;
        pair<int,int> destination;
        source = {0,0};
        destination = {n-1,n-1};
        queue<pair<int,pair<int,int>>> q;
        int  delRow[] = {-1,-1,-1,0,0,0,1,1,1};
        int delCol[] = {-1,0,1,-1,0,1,-1,0,1};
        vector<vector<int>> dis(n, vector<int>(n,1e9));
        dis[source.first][source.second] = 1;
        q.push({0,{source.first,source.second}});

        while(!q.empty()){
            auto it = q.front();
            int distance = it.first;
            int row = it.second.first;
            int col = it.second.second;
            q.pop();


            for(int i = 0; i < 9; i++){
                int nRow = row + delRow[i];
                int nCol = col + delCol[i];

                if(nRow >=0 && nCol >=0 && nRow < n && nCol < n && grid[nRow][nCol] == 0 && dis[nRow][nCol] > 1 + distance ){
                dis[nRow][nCol] = 1 + distance;
                if(nRow == destination.first && nCol == destination.second){
                    return 1 + dis[nRow][nCol];
                }
                q.push({1 + distance, {nRow,nCol}});
                }
            }

        }
        return -1;
    }

Complexity Analysis:

Time: O(N^2)
Space: O(N^2)

Feel free to let me know if you have any questions or need further clarification. Happy problem-solving!