-
Notifications
You must be signed in to change notification settings - Fork 27
/
Distance of nearest cell having 1.cpp
57 lines (51 loc) · 1.93 KB
/
Distance of nearest cell having 1.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
/* Link to the "Distance of nearest cell having 1" Problem ==>> https://practice.geeksforgeeks.org/problems/distance-of-nearest-cell-having-1-1587115620/1
Link to the complete Explaination Video ==>> https://youtu.be/7xsRW8x-ACo */
class Solution{
public:
vector<vector<int>>nearest(vector<vector<int>>grid){
queue<pair<int,int>> q;
vector<vector<int>>grid2 =grid;
int r = grid.size();
int c = grid[0].size();
int level = 0,rtemp,ctemp,size;
for(int i=0;i<r;++i){
for(int j=0;j<c;++j){
if(grid[i][j]==1)
q.push({i,j});
}
}
while(!q.empty()){
++level;
size=q.size();
while(size-->0){
rtemp = q.front().first;
ctemp = q.front().second;
q.pop();
if(rtemp>0 && grid[rtemp-1][ctemp]==0){
q.push({rtemp-1,ctemp});
grid[rtemp-1][ctemp]=level;
}
if(ctemp>0 && grid[rtemp][ctemp-1]==0){
q.push({rtemp,ctemp-1});
grid[rtemp][ctemp-1]=level;
}
if(rtemp<r-1 && grid[rtemp+1][ctemp]==0){
q.push({rtemp+1,ctemp});
grid[rtemp+1][ctemp]=level;
}
if(ctemp<c-1 && grid[rtemp][ctemp+1]==0){
q.push({rtemp,ctemp+1});
grid[rtemp][ctemp+1]=level;
}
}
}
for(int i=0;i<r;++i){
for(int j=0;j<c;++j){
if(grid2[i][j]==1){
grid[i][j]=0;
}
}
}
return grid;
}
};