LeetCode/orangesRotting at master · Abhishek2003ij/LeetCode · 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
class Solution {
    public int orangesRotting(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        Queue<Pair<Integer,Integer>> q = new LinkedList<>();
        int[][] vis = new int[n][m];
        int found=0;
        int temp=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]==2)
                {
                    q.add(new Pair<>(i,j));
                }
                else{
                    vis[i][j]=0;
                    if(grid[i][j]==1)
                    {
                        found++;
                    }
                }
            }
        }
        int[] row = {-1,0,1,0};
        int[] col = {0,1,0,-1};
        while(!q.isEmpty())
        {
            boolean yes=false;
            int size= q.size();
            for(int i=0;i<size;i++)
            {
            Pair<Integer,Integer> cur = q.poll();
            int r = cur.getKey();
            int c = cur.getValue();
            for(int j=0;j<4;j++)
            {
                int dr = r + row[j];
                int dc = c+col[j];
                if(dr>=0 && dr<n && dc>=0 && dc<m && grid[dr][dc]==1 && vis[dr][dc]!=2)
                {
                    q.add(new Pair<>(dr,dc));
                    vis[dr][dc]=2;
                    found--;
                    yes=true;
                }
            }

        }
          if(yes)
            {
                temp++;
            }
        }
        return (found==0)?temp:-1;

    }
}