-
Notifications
You must be signed in to change notification settings - Fork 0
/
Bfs.cpp
95 lines (52 loc) · 1.42 KB
/
Bfs.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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
vector < vector < int > > nearest(vector < vector < int >> & mat, int n, int m) {
// Write your code here.
vector < vector < int > >vis(n,vector<int>(m,0));
vector < vector < int > >dist(n,vector<int>(m,0));
queue<pair<int,int>>q;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mat[i][j]==1){
q.push({i,j});
dist[i][j]=0;
}
}
}
vector<int>dx={-1,0,1,0};
vector<int>dy={0,-1,0,1};
while(!q.empty()){
int row=q.front().first;
int col=q.front().second;
q.pop();
vis[row][col]=1;
for(int i=0;i<4;i++){
int nrow=row+dx[i];
int ncol=col+dy[i];
if(nrow>=0 && ncol>=0 && nrow<n && ncol<m && !vis[nrow][ncol]&& mat[nrow][ncol]==0){
vis[nrow][ncol]=1;
mat[nrow][ncol]=1;
dist[nrow][ncol]=dist[row][col]+1;
q.push({nrow,ncol});
}
}
}
return dist;
}
// queue<int> q;
// vector<bool> used(n);
// vector<int> d(n), p(n);
// q.push(s);
// used[s] = true;
// p[s] = -1;
// while (!q.empty()) {
// int v = q.front();
// q.pop();
// for (int u : adj[v]) {
// if (!used[u]) {
// used[u] = true;
// q.push(u);
// d[u] = d[v] + 1;
// p[u] = v;
// }
// }
// }
// ```