-
Notifications
You must be signed in to change notification settings - Fork 9
/
Shortest Path in Binary Matrix.cpp
36 lines (35 loc) · 1.09 KB
/
Shortest Path in Binary Matrix.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
https://leetcode.com/problems/shortest-path-in-binary-matrix/
*/
class Solution {
private:
vector<vector<int>> dir={{-1,0},{1,0},{0,-1},{0,1},{1,1},{-1,-1},{-1,1},{1,-1}};
struct queueNode{
int x;
int y;
int dist;
};
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int n=grid.size();
if(grid[0][0]!=0||grid[n-1][n-1]!=0) return -1;
vector<vector<bool>> visited(n,vector<bool>(n,false));
visited[n-1][n-1]=true;
queue<queueNode> q;
queueNode s={n-1,n-1,1};
q.push(s);
while(!q.empty()){
queueNode curr=q.front();q.pop();
int x=curr.x,y=curr.y;
if(x==0&&y==0) return curr.dist;
for(int i=0;i<dir.size();i++){
int row=x+dir[i][0],col=y+dir[i][1];
if(row>=n||col>=n||row<0||col<0||grid[row][col]==1||visited[row][col]) continue;
visited[row][col]=true;
queueNode adjcell={row,col,curr.dist+1};
q.push(adjcell);
}
}
return -1;
}
};