|
| 1 | +importjava.util.HashSet; |
| 2 | +importjava.util.LinkedList; |
| 3 | +importjava.util.Objects; |
| 4 | +importjava.util.Queue; |
| 5 | +importjava.util.Set; |
| 6 | + |
| 7 | +publicclassRottingOranges { |
| 8 | +privatestaticfinalintEMPTY_CELL =0; |
| 9 | +privatestaticfinalintFRESH_ORANGE =1; |
| 10 | +privatestaticfinalintROTTEN_ORANGE =2; |
| 11 | + |
| 12 | +privatestaticfinalclassOrange { |
| 13 | +privatefinalintrow; |
| 14 | +privatefinalintcolumn; |
| 15 | +privatefinalintminutes; |
| 16 | + |
| 17 | +privateOrange(introw,intcolumn,intminutes) { |
| 18 | +this.row =row; |
| 19 | +this.column =column; |
| 20 | +this.minutes =minutes; |
| 21 | + } |
| 22 | + |
| 23 | +@Override |
| 24 | +publicbooleanequals(Objectobj) { |
| 25 | +if (obj ==this)returntrue; |
| 26 | +if (obj ==null ||obj.getClass() !=this.getClass())returnfalse; |
| 27 | +varthat = (Orange)obj; |
| 28 | +returnthis.row ==that.row &&this.column ==that.column; |
| 29 | + } |
| 30 | + |
| 31 | +@Override |
| 32 | +publicinthashCode() { |
| 33 | +returnObjects.hash(row,column); |
| 34 | + } |
| 35 | + } |
| 36 | + |
| 37 | +publicstaticintorangesRotting(int[][]grid) { |
| 38 | +finalQueue<Orange>oranges =allRottingOranges(grid); |
| 39 | +finalSet<Orange>visited =newHashSet<>(); |
| 40 | +intresult =0; |
| 41 | +while (!oranges.isEmpty()) { |
| 42 | +Orangeorange =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(newOrange(orange.row -1,orange.column,orange.minutes +1)); |
| 49 | +oranges.add(newOrange(orange.row,orange.column +1,orange.minutes +1)); |
| 50 | +oranges.add(newOrange(orange.row +1,orange.column,orange.minutes +1)); |
| 51 | +oranges.add(newOrange(orange.row,orange.column -1,orange.minutes +1)); |
| 52 | +result =Math.max(result,orange.minutes); |
| 53 | + } |
| 54 | +if (allAreRotten(grid))returnresult; |
| 55 | +return -1; |
| 56 | + } |
| 57 | + |
| 58 | +privatestaticbooleanallAreRotten(int[][]grid) { |
| 59 | +for (int[]row :grid) { |
| 60 | +for (intorange :row) { |
| 61 | +if (orange ==FRESH_ORANGE)returnfalse; |
| 62 | + } |
| 63 | + } |
| 64 | +returntrue; |
| 65 | + } |
| 66 | + |
| 67 | +privatestaticQueue<Orange>allRottingOranges(int[][]grid) { |
| 68 | +finalQueue<Orange>rottenOranges =newLinkedList<>(); |
| 69 | +for (introw =0 ;row <grid.length ;row++) { |
| 70 | +for (intcolumn =0 ;column <grid[0].length ;column++) { |
| 71 | +if (grid[row][column] ==ROTTEN_ORANGE) { |
| 72 | +rottenOranges.add(newOrange(row,column,0)); |
| 73 | + } |
| 74 | + } |
| 75 | + } |
| 76 | +returnrottenOranges; |
| 77 | + } |
| 78 | + |
| 79 | +privatestaticbooleanisValidPosition(Orangeorange,int[][]grid) { |
| 80 | +returnorange.row >=0 &&orange.row <grid.length &&orange.column >=0 &&orange.column <grid[0].length; |
| 81 | + } |
| 82 | + |
| 83 | +privatestaticbooleanisRotten(int[][]grid,Orangeorange) { |
| 84 | +returngrid[orange.row][orange.column] ==ROTTEN_ORANGE; |
| 85 | + } |
| 86 | + |
| 87 | +privatestaticbooleanisEmptyCell(int[][]grid,Orangeorange) { |
| 88 | +returngrid[orange.row][orange.column] ==EMPTY_CELL; |
| 89 | + } |
| 90 | +} |