Data-Structures/graph_bfs_nearest_1.java at main · Jaiyadav88/Data-Structures · GitHub

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
/*
 * Distance of nearest cell having 1
 *
 * Given a binary grid of n*m. Find the distance of the nearest 1 in the grid for each cell.
   The distance is calculated as |i1  - i2| + |j1 - j2|, where i1, j1 are the row number and column number of the current cell, an   d i2,j2 are the row number and column number of the nearest cell having value 1. There should be atleast one 1 in the grid.

Example 1:

Input: grid = {{0,1,1,0},{1,1,0,0},{0,0,1,1}}
Output: {{1,0,0,1},{0,0,1,1},{1,1,0,0}}
Explanation: The grid is-
0 1 1 0
1 1 0 0
0 0 1 1
0's at (0,0), (0,3), (1,2), (1,3), (2,0) and
(2,1) are at a distance of 1 from 1's at (0,1),
(0,2), (0,2), (2,3), (1,0) and (1,1)
respectively.

Example 2:

Input: grid = {{1,0,1},{1,1,0},{1,0,0}}
Output: {{0,1,0},{0,0,1},{0,1,2}}
Explanation: The grid is-
1 0 1
1 1 0
1 0 0
0's at (0,1), (1,2), (2,1) and (2,2) are at a
distance of 1, 1, 1 and 2 from 1's at (0,0),
(0,2), (2,0) and (1,1) respectively.

*/
class Pair
{
    int a;int b;int step;
    public Pair(int a,int b,int s)
    {
        this.a=a;
        this.b=b;
        this.step=s;
    }
}
class Solution
{
    //Function to find distance of nearest 1 in the grid for each cell.
    public int[][] nearest(int[][] grid)
    {
        boolean visited[][]=new boolean[grid.length][grid[0].length];
        int res[][]=new int[grid.length][grid[0].length];
        //using BFS
        Queue<Pair> q=new LinkedList();
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(grid[i][j]==1)
                {
                    q.offer(new Pair(i,j,0));
                    visited[i][j]=true;
                }
            }
        }
        int delrow[]={-1,0,+1,0};
        int delcol[]={0,+1,0,-1};
        while(!q.isEmpty())
        {
           Pair p=q.poll();
           int a=p.a;
           int b=p.b;
           int step=p.step;
           res[a][b]=step;
           for(int i=0;i<4;i++)
           {
               int nrow=a+delrow[i];
               int ncol=b+delcol[i];
               if(nrow>=0&&nrow<grid.length&&ncol>=0&&ncol<grid[0].length&&visited[nrow][ncol]==false)
               {
                   q.offer(new Pair(nrow,ncol,step+1));
                   visited[nrow][ncol]=true;
               }
           }
        }
        return res;
    }
}