|
| 1 | +import java.util.HashSet; |
| 2 | +import java.util.LinkedList; |
| 3 | +import java.util.Objects; |
| 4 | +import java.util.Queue; |
| 5 | +import java.util.Set; |
| 6 | + |
| 7 | +public class RottingOranges { |
| 8 | + private static final int EMPTY_CELL = 0; |
| 9 | + private static final int FRESH_ORANGE = 1; |
| 10 | + private static final int ROTTEN_ORANGE = 2; |
| 11 | + |
| 12 | + private static final class Orange { |
| 13 | + private final int row; |
| 14 | + private final int column; |
| 15 | + private final int minutes; |
| 16 | + |
| 17 | + private Orange(int row, int column, int minutes) { |
| 18 | + this.row = row; |
| 19 | + this.column = column; |
| 20 | + this.minutes = minutes; |
| 21 | + } |
| 22 | + |
| 23 | + @Override |
| 24 | + public boolean equals(Object obj) { |
| 25 | + if (obj == this) return true; |
| 26 | + if (obj == null || obj.getClass() != this.getClass()) return false; |
| 27 | + var that = (Orange) obj; |
| 28 | + return this.row == that.row && this.column == that.column; |
| 29 | + } |
| 30 | + |
| 31 | + @Override |
| 32 | + public int hashCode() { |
| 33 | + return Objects.hash(row, column); |
| 34 | + } |
| 35 | + } |
| 36 | + |
| 37 | + public static int orangesRotting(int[][] grid) { |
| 38 | + final Queue<Orange> oranges = allRottingOranges(grid); |
| 39 | + final Set<Orange> visited = new HashSet<>(); |
| 40 | + int result = 0; |
| 41 | + while (!oranges.isEmpty()) { |
| 42 | + Orange orange = oranges.poll(); |
| 43 | + if (!isValidPosition(orange, grid) || visited.contains(orange) || isEmptyCell(grid, orange)) { |
| 44 | + continue; |
| 45 | + } |
| 46 | + visited.add(orange); |
| 47 | + grid[orange.row][orange.column] = ROTTEN_ORANGE; |
| 48 | + oranges.add(new Orange(orange.row - 1, orange.column, orange.minutes + 1)); |
| 49 | + oranges.add(new Orange(orange.row, orange.column + 1, orange.minutes + 1)); |
| 50 | + oranges.add(new Orange(orange.row + 1, orange.column, orange.minutes + 1)); |
| 51 | + oranges.add(new Orange(orange.row, orange.column - 1, orange.minutes + 1)); |
| 52 | + result = Math.max(result, orange.minutes); |
| 53 | + } |
| 54 | + if (allAreRotten(grid)) return result; |
| 55 | + return -1; |
| 56 | + } |
| 57 | + |
| 58 | + private static boolean allAreRotten(int[][] grid) { |
| 59 | + for (int[] row : grid) { |
| 60 | + for (int orange : row) { |
| 61 | + if (orange == FRESH_ORANGE) return false; |
| 62 | + } |
| 63 | + } |
| 64 | + return true; |
| 65 | + } |
| 66 | + |
| 67 | + private static Queue<Orange> allRottingOranges(int[][] grid) { |
| 68 | + final Queue<Orange> rottenOranges = new LinkedList<>(); |
| 69 | + for (int row = 0 ; row < grid.length ; row++) { |
| 70 | + for (int column = 0 ; column < grid[0].length ; column++) { |
| 71 | + if (grid[row][column] == ROTTEN_ORANGE) { |
| 72 | + rottenOranges.add(new Orange(row, column, 0)); |
| 73 | + } |
| 74 | + } |
| 75 | + } |
| 76 | + return rottenOranges; |
| 77 | + } |
| 78 | + |
| 79 | + private static boolean isValidPosition(Orange orange, int[][] grid) { |
| 80 | + return orange.row >= 0 && orange.row < grid.length && orange.column >= 0 && orange.column < grid[0].length; |
| 81 | + } |
| 82 | + |
| 83 | + private static boolean isRotten(int[][] grid, Orange orange) { |
| 84 | + return grid[orange.row][orange.column] == ROTTEN_ORANGE; |
| 85 | + } |
| 86 | + |
| 87 | + private static boolean isEmptyCell(int[][] grid, Orange orange) { |
| 88 | + return grid[orange.row][orange.column] == EMPTY_CELL; |
| 89 | + } |
| 90 | +} |
0 commit comments