Shortest Path in Binary Matrix | February Leetcoding Challenge 2021 | Day 13
logo
Manas Sinha
Developer | Designer

By Manas | 13 February 2021

February LeetCoding Challenge 2021

Day 13

Shortest Path in Binary Matrix

PROBLEM  STATEMENT:
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. Example 1
Input: [[0,1],[1,0]]


Output: 2

Example 2
Input: [[0,0,0],[1,1,0],[1,1,0]]


Output: 4


Note:
  1. 1 <= grid.length == grid[0].length <= 100
  2. grid[r][c] is 0 or 1

Explanation

A grid can also be visualised as a graph with every cell as a node connected with every adjacent cell. Keeping this in mind we can apply graph algorithms on a grid quite easily. So to find a shortest path between two nodes in this grid (which is a undirected graph) we can simply apply BFS and return the path length.
ALGORITHM:
  • If the source node or destination node has value “1” return -1
  • Insert the first node [0,0] in the queue to start the BFS and update its value as “1”. We will use the grid itself to store the path length.
  • Pop the front node of the queue and push every node adjacent to this front node whose grid value is not ‘1’.
  • Update the value of the node being inserted in the queue as value of parent node + 1
  • If destination is reached return the value grid[N-1][N-1]
 
In this approach we don’t care about all the possible paths. If you observe closely, every time we are moving one level below the current level so the distance of every node in current level from the source node is one more than the distance of their parent node from the source [dist(curr_node,src) = dist(parent[curr_node],src) + 1]. So once we reach the destination node we return the path length as any path after this will contain node from level below the current level and hence have a greater path length.

code

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int N = grid.size();

        
        if (grid[0][0] == 1 || grid[N-1][N-1] == 1)
            return -1;

        queue<pair<int, int>> q;
        q.push(make_pair(0,0)); 
        
        int dirs[8][2] = {{1,1}, {0,1},{1,0},{0,-1},{-1,0},{-1, -1},{1, -1},{-1, 1}};
        
        grid[0][0] = 1; 

        while(!q.empty()){
            int row = q.front().first;
            int col = q.front().second;
            
            q.pop();
            
            if(row == N -1 && col == N -1)
                return grid[N-1][N-1];

            
            for(auto dir : dirs){
                int i = row + dir[0];
                int j = col + dir[1];

                
                if(i >= 0 && i < N && j >= 0 && j < N && grid[i][j] == 0){
                    q.push(make_pair(i,j));
                    
                    grid[i][j] = grid[row][col] + 1; 
                }
            }

            
        }

        
        return -1;
    }
};

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply