This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #1091 (Medium): 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_iandC_{i+1}are connected 8-directionally (ie., they are different and share an edge or corner) -
C_1is at location(0, 0)(ie. has valuegrid[0][0]) -
C_kis at location(N-1, N-1)(ie. has valuegrid[N-1][N-1]) - If
C_iis located at(r, c), thengrid[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 2: | |
|---|---|
| Input: | [[0,0,0],[1,1,0],[1,1,0]] |
| Output: | 4 |
| Visual: |  |
Constraints:
1 <= grid.length == grid[0].length <= 100-
grid[r][c]is0or1
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.
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 1s.
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.
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:
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:
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:
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:
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;
}
};
Top comments (0)