-
Notifications
You must be signed in to change notification settings - Fork 1
/
15_October.cpp
34 lines (34 loc) · 1.36 KB
/
15_October.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
class Solution {
using pii=pair<int,int>;
vector<vector<int>> dis={{0,-1},{-1,0},{0,1},{1,0}};
bool isValid(int x,int y,int m,int n){
return x>=0 and y>=0 and x<m and y<n;
}
public:
int shortestPath(vector<vector<int>> &A, pair<int, int> source,
pair<int, int> destination) {
int m=A.size(),n=A[0].size();
queue<pii> q;
q.push(source);
A[source.first][source.second]=0;
int k=0;
while(q.size()){
int len=q.size();
while(len--){
pii pair=q.front();q.pop();
if(pair==destination) return k;
auto i=pair.first,j=pair.second;
for(auto &it:dis){
auto x=i+it[0];
auto y=j+it[1];
if(isValid(x,y,m,n) and A[x][y]){
q.push({x,y});
A[x][y]=0;
}
}
}
k++;
}
return -1;
}
};