D-9.md

🔮 Question - Rotting Oranges

In a given grid, each cell can have one of three values:
the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:

Input: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

🐉 Solution

class Solution {
    public int orangesRotting(int[][] grid) {
       Set<String> fresh=new HashSet<>();
     Set<String> rotten=new HashSet<>();
        int i,j,minutes=0;
        for(i=0;i<grid.length;i++){
            for(j=0;j<grid[i].length;j++){
                if(grid[i][j]==1){
                    fresh.add(""+i+j);
                }
                else if(grid[i][j]==2){
                    rotten.add(""+i+j);
                }
            }
        }
        int directions[][]={{0,1},{1,0},{-1,0},{0,-1}};
        while(fresh.size()>0){
            Set<String> infected=new HashSet<>();
            for(String rot:rotten){
                i=rot.charAt(0)-'0';
               j=rot.charAt(1)-'0';
                for(int dir[]:directions){
                    int nextI=i+dir[0];
                    int nextJ=j+dir[1];
                    if(fresh.contains(""+nextI+nextJ)){
                        fresh.remove(""+nextI+nextJ);
                        infected.add(""+nextI+nextJ);
                    }
                }
            }
            if(infected.size()==0){
                return -1;
            }
            rotten=infected;
            minutes++;
        }
        return minutes;
    }
}