Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- int freshCount = 0;
- Queue<Pair> queue = new LinkedList<>();
- public int orangesRotting(int[][] grid) {
- for (int i = 0; i < grid.length; i++) {
- for (int j = 0; j < grid[i].length; j++) {
- if (grid[i][j] == 2) {
- queue.offer(new Pair(i,j)); // Rotten oranges
- }
- if (grid[i][j] == 1) freshCount++;
- }
- }
- int count = 0;
- while (!queue.isEmpty()) {
- rotOranges(grid);
- count++;
- }
- if (freshCount > 0) return -1;
- return count == 0 ? count : count-1;
- }
- private void rotOranges(int[][] grid) {
- int size = queue.size();
- for (int i = 0; i < size; i++) {
- Pair indexes = queue.poll();
- List<Pair> nextRotten = getAlongSide(grid, indexes.i, indexes.j);
- for(Pair p: nextRotten) {
- grid[p.i][p.j] = 2;
- freshCount--;
- queue.offer(p);
- }
- }
- }
- public List<Pair> getAlongSide(int[][] grid, int i, int j) {
- List<Pair> result = new ArrayList<>();
- if (isSafeDown(grid, i, j)) result.add(new Pair(i+1, j));
- if (isSafeUp(grid, i, j)) result.add(new Pair(i-1, j));
- if (isSafeLeft(j, grid[i])) result.add(new Pair(i, j+1));
- if (isSafeRight(j, grid[i])) result.add(new Pair(i, j-1));
- return result;
- }
- private static boolean isSafeUp(int[][] grid, int i, int j) {
- return i - 1 >= 0 && grid[i - 1][j] == 1;
- }
- private static boolean isSafeRight(int j, int[] grid) {
- return j - 1 >= 0 && grid[j - 1] == 1;
- }
- private static boolean isSafeDown(int[][] grid, int i, int j) {
- return i + 1 < grid.length && grid[i + 1][j] == 1;
- }
- private static boolean isSafeLeft(int j, int[] grid) {
- return j + 1 < grid.length && grid[j + 1] == 1;
- }
- }
- class Pair {
- int i, j;
- public Pair(int i, int j) {
- this.i = i;
- this.j = j;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement