Solution: Shortest Path in Binary Matrix
Tags: algorithms, javascript, java, leetcode
Published: 2021-02-13 12:41:38

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/shortest-path-in-binary-matrix/discuss/1063571).*

---

####[Leetcode Problem #1091 (*Medium*): Shortest Path in Binary Matrix](https://leetcode.com/problems/shortest-path-in-binary-matrix/)

---

***Description:***

*In an `N` by `N` square grid, each cell is either empty (0) or blocked (1).*

*A clear path from top-left to bottom-right has length `k` if and only if it is composed of cells `C_1, C_2, ..., C_k` such that:*

  -  *Adjacent cells `C_i` and `C_{i+1}` are connected 8-directionally (ie., they are different and share an edge or corner)*
  -  *`C_1` is at location `(0, 0)` (ie. has value `grid[0][0]`)*
  -  *`C_k` is at location `(N-1, N-1)` (ie. has value `grid[N-1][N-1]`)*
  -  *If `C_i` is located at `(r, c)`, then `grid[r][c]` is empty (ie. `grid[r][c] == 0`).*

*Return the length of the shortest such clear path from top-left to bottom-right.  If such a path does not exist, return -1.*

---

***Examples:***

Example 1:||
|---:|---|
*Input:*|[[0,1],[1,0]]
*Output:*|2
*Visual:*|![Example 1 Visual](https://dev-to-uploads.s3.amazonaws.com/i/jeizxf6vs1als4lyrioc.png)

Example 2:||
|---:|---|
*Input:*|[[0,0,0],[1,1,0],[1,1,0]]
*Output:*|4
*Visual:*|![Example 2 Visual](https://dev-to-uploads.s3.amazonaws.com/i/53d26flyyzhgkag5ivub.png)

---

***Constraints:***
 - `1 <= grid.length == grid[0].length <= 100`
 - `grid[r][c]` is `0` or `1`

---

***Idea:***

When we're asked about finding the "shortest path", the first thing that should come to mind is a **breadth-first solution** (BFS) approach. In a standard graph BFS solution, we set up a **queue** (**q**) and fill it with our starting position (**grid[0][0]**). Then we keep pulling entries from **q**, figuring out the next moves from that position, and input those next moves back into **q**.

When we're ready to start, we can change **grid[0][0]** to **1**, then as we reach new cells, we can store the distance to that cell in the cell at the same time we add it to the queue. The distance will simply be one more than the distance to the cell we're moving from. This will also eliminate duplicate queue entries by changing visited cells to a non-zero number.

Through the nature of a BFS approach to graph traversal (with non-weighted edges), the first time we reach the end location (**grid[n][n]**) will represent the best possible distance.

Since **0 <= i, j <= 100**, both **i** and **j** will fit into **7 bits** each, so we can utilize **bit manipulation** to store both in one integer. With a **bitwise left shift** (**<<**) we can move the value of **j** to the left by **7 bits** before adding it to **i** to allow for both to fit in **14 bits** of an integer.
```js
Bitwise shift example:

   i  =  93 (base 10)  =  1011101 (base 2)
   j  =  75 (base 10)  =  1001011 (base 2)

   j << 7  =  1001011<<<<<<<     // Bitwise left shift moves the value left
           =  10010110000000     // And fills in the space with 0s

   i:                           1011101 
        j << 7:       +  10010110000000
                        ----------------
   i + (j << 7):      =  10010111011101 (base 2)
                      =            9693 (base 10)
```
To read **i** from the first **7 bits** of our stored integer again, you can use **bitwise AND** (**&**) and a **bitmask** of **1111111**. The easiest way to get a bitmask of **1111111** is to shift a single bit to the left by **7** (**1 << 7 = 10000000**) and then subtract **1**, rolling it back to all **1**s.
```js
Bitmask example:

   1 << 7:               10000000
                      -         1
                        ----------
   (1 << 7) - 1:      =   1111111
```
The bitwise AND will only keep any bits that have a **1** in both numbers, thus stripping away anything except the first **7 bits** of data.
```js
Bitwise AND example:

      10010111011101
   &         1111111
     ----------------
   =         1011101
```
To read the **j** value from our integer, we can just shift it to the right by **7 bits**, which will throw away the first **7 bits** of data corresponding to the **i** value.

If **q** becomes empty without finding a path to the end, then **return -1**.

---

***Implementation:***

If either the starting point or the ending point are a **1**, then we quickly **return -1**.

To check which moves can be made, we can just iterate over a three-value range for each **i** and **j**, and to make sure that they remain in bounds, we can apply a **max** and **min** to the range.

---

***Javascript Code:***
```javascript
var shortestPathBinaryMatrix = function(grid) {
    let n = grid.length - 1, q = [0]
    if (grid[0][0] || grid[n][n]) return -1
    grid[0][0] = 1
    while (q.length) {
        let curr = q.shift(), i = curr & (1 << 7) - 1, j = curr >> 7
        if (i === n && j === n) return grid[n][n]
        for (let a = Math.max(i-1,0); a <= Math.min(i+1,n); a++)
            for (let b = Math.max(j-1,0); b <= Math.min(j+1,n); b++)
                if (grid[a][b] === 0)
                    grid[a][b] = grid[i][j] + 1, q.push(a + (b << 7))
    }
    return -1
};
```

---

***Python Code:***
```python
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)-1
        if grid[0][0] or grid[n][n]: return -1
        q, grid[0][0] = [0], 1
        while len(q):
            curr = q.pop(0)
            i, j = curr & ((1 << 7) - 1), curr >> 7
            if i == n and j == n: return grid[n][n]
            for a in range(max(i-1,0),min(i+2,n+1)):
                for b in range(max(j-1,0),min(j+2,n+1)):
                    if grid[a][b] == 0:
                        grid[a][b] = grid[i][j] + 1
                        q.append(a + (b << 7))
        return -1
```

---

***Java Code:***
```java
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length - 1;
        Queue<Integer> q = new ArrayDeque<Integer>();
        q.add(0);
        if (grid[0][0] == 1 || grid[n][n] == 1) return -1;
        grid[0][0] = 1;
        while (q.size() > 0) {
            int curr = q.remove(), i = curr & (1 << 7) - 1, j = curr >> 7;
            if (i == n && j == n) return grid[n][n];
            for (int a = Math.max(i-1,0); a <= Math.min(i+1,n); a++)
                for (int b = Math.max(j-1,0); b <= Math.min(j+1,n); b++)
                    if (grid[a][b] == 0) {
                        grid[a][b] = grid[i][j] + 1;
                        q.add(a + (b << 7));
                    }
        }
        return -1;
    }
}
```

---

***C++ Code:***
```c++
class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int m = grid.size(), n = m - 1;
        std::queue<int> q;
        q.push(0);
        if (grid[0][0] == 1 || grid[n][n] == 1) return -1;
        grid[0][0] = 1;
        while (q.size() > 0) {
            int curr = q.front();
            q.pop();
            int i = curr & (1 << 7) - 1, j = curr >> 7;
            if (i == n && j == n) return grid[n][n];
            for (int a = std::max(i-1,0); a <= std::min(i+1,n); a++)
                for (int b = std::max(j-1,0); b <= std::min(j+1,n); b++)
                    if (grid[a][b] == 0) {
                        grid[a][b] = grid[i][j] + 1;
                        q.push(a + (b << 7));
                    }
        }
        return -1;
    }
};
```