## 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`

).

**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 <= grid.length == grid[0].length <= 100`

`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;
}
};
```