DAY 41 - Shortest Path in a Binary Matrix
Tags: coding, leetcode, cpp, tutorial
Published: 2023-07-14 17:12:54

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](https://leetcode.com/problems/shortest-path-in-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:_**


> - ![Example 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bbqqr9m3w8stu7x69rd1.png)
> - Input: grid = [[0,1],[1,0]]
> - Output: 2

--- 

**_Example 2:_**


> - ![Example 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a0uvt89hb4g54ge2142n.png)

> - 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!