-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathFind shortest safe route in a matrix
56 lines (55 loc) · 1.41 KB
/
Find shortest safe route in a matrix
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution
{
public:
int findShortestPath(vector<vector<int>> &mat)
{
// code here
int n=mat.size();
int m=mat[0].size();
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(mat[i][j]==0)
{
if(i-1>=0)
mat[i-1][j]=-1;
if(i+1<n)
mat[i+1][j]=-1;
if(j-1>=0)
mat[i][j-1]=-1;
if(j+1<m)
mat[i][j+1]=-1;
}
}
}
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
queue<pair<int,pair<int,int>>> q;
vector<vector<int>> vis(n,vector<int>(m,0));
for(int i=0; i<n; i++)
{
if(mat[i][0]==1)
q.push({1,{i,0}});
}
while(q.size())
{
auto temp=q.front();
q.pop();
int dis=temp.first;
int i=temp.second.first;
int j=temp.second.second;
vis[i][j]=1;
if(j==m-1)
return dis;
for(int k=0; k<4; k++)
{
int x=i+dx[k];
int y=j+dy[k];
if(x>=0 && x<n && y>=0 && y<m && vis[x][y]==0 && mat[x][y]==1)
q.push({dis+1,{x,y}});
}
}
return -1;
}
};