-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDistance of nearest cell having 1 (GFG)
52 lines (51 loc) · 1.5 KB
/
Distance of nearest cell having 1 (GFG)
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
class Solution
{
public:
class Point {
public:
int x, y;
Point(int _x, int _y) {
x = _x;
y = _y;
}
};
//Function to find distance of nearest 1 in the grid for each cell.
vector<vector<int>>nearest(vector<vector<int>>grid)
{
// Code here
queue<Point> Queue;
int n = grid.size();
int m = grid[0].size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == 1) {
Queue.push(Point(i, j));
}
grid[i][j] = -1;
}
}
int ans = -1;
while(!Queue.empty()) {
int sz = Queue.size();
ans++;
for(int k = 0; k < sz; k++) {
Point temp = Queue.front();
Queue.pop();
int i = temp.x;
int j = temp.y;
if(grid[i][j] == -1) {
if(i - 1 >= 0 && i - 1 < n && j >= 0 && j < m && grid[i - 1][j] == -1)
Queue.push(Point(i - 1, j));
if(i + 1 >= 0 && i + 1 < n && j >= 0 && j < m && grid[i + 1][j] == -1)
Queue.push(Point(i + 1, j));
if(i >= 0 && i < n && j - 1 >= 0 && j - 1 < m && grid[i][j - 1] == -1)
Queue.push(Point(i, j - 1));
if(i >= 0 && i < n && j + 1 >= 0 && j + 1 < m && grid[i][j + 1] == -1)
Queue.push(Point(i, j + 1));
grid[i][j] = ans;
}
}
}
return grid;
}
};