Rotting Oranges

class Solution {
    // Function to propagate rot process in the grid
    public boolean propagateRot(int currentMinute, int[][] orchard, int totalRows, int totalCols) {
        int[][] steps = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        boolean continueRotting = false;
        for (int r = 0; r < totalRows; ++r)
            for (int c = 0; c < totalCols; ++c)
                if (orchard[r][c] == currentMinute)
                    for (int[] move : steps) {
                        int newRow = r + move[0], newCol = c + move[1];
                        if (newRow >= 0 && newRow < totalRows && newCol >= 0 && newCol < totalCols)
                            if (orchard[newRow][newCol] == 1) {
                                orchard[newRow][newCol] = currentMinute + 1;
                                continueRotting = true;
                            }
                    }
        return continueRotting;
    }

    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int minute = 2;
        while (propagateRot(minute, grid, rows, cols))
            minute++;

        for (int[] orchardRow : grid)
            for (int orangeState : orchardRow)
                if (orangeState == 1)
                    return -1;

        return minute - 2;
    }
}

The Rotting Oranges problem involves a grid where each cell can contain an orange that can be fresh, rotten, or empty. The goal is to determine the minimum number of minutes required for all fresh oranges to become rotten, given that a rotten orange at each minute turns its adjacent fresh oranges rotten.

The given solution in Java provides an efficient approach for solving this problem:

1. Define the propagateRot function to simulate the rotting process for each minute:

   • Pass the current minute, orchard (grid), total rows, and total columns as parameters.
   • Use the steps array to represent possible movements: up, right, down, and left.
   • Iterate over each cell in the grid. If an orange turns rotten at the current minute, use the steps to try and rot adjacent oranges.
   • If any fresh orange rots during this process, set a flag to true, indicating that the process needs to continue into the next minute.

2. Define the orangesRotting function to manage the propagation over multiple minutes and determine if all oranges can rot:

   • Initialize minute counters and dimensions of the grid.
   • Continuously call propagateRot while tracking each minute until no fresh oranges can be rotten.
   • After exiting the loop, recheck if any fresh oranges are still left, indicating that not all can be rotten.
   • Calculate the elapsed minutes since starting rotting (not counting the initial state and the first propagation minute passed).

By carefully managing the simulation of each minute and checking termination conditions, this solution efficiently determines how quickly all oranges can rot or if it's impossible, ensuring optimal time usage and clarity in processing the grid-based simulation.

class Solution:
    def rotOranges(self, matrix: List[List[int]]) -> int:
        max_rows, max_cols = len(matrix), len(matrix[0])

        moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        def spreadRotten(current_time):
            continue_process = False
            for r in range(max_rows):
                for c in range(max_cols):
                    if matrix[r][c] == current_time:
                        for move in moves:
                            new_r, new_c = r + move[0], c + move[1]
                            if 0 <= new_r < max_rows and 0 <= new_c < max_cols:
                                if matrix[new_r][new_c] == 1:
                                    matrix[new_r][new_c] = current_time + 1
                                    continue_process = True
            return continue_process

        time_counter = 2
        while spreadRotten(time_counter):
            time_counter += 1

        for row in matrix:
            if 1 in row:
                return -1

        return time_counter - 2

The provided Python code defines a solution for the "Rotting Oranges" problem, where the goal is to find out the minimum number of minutes needed until all non-rotten oranges become rotten if it is possible at all.

Here's how the code works:

• Read the matrix dimensions and define possible moves (right, down, left, up) using coordinate adjustments.
• The spreadRotten function, when called with the current time, checks all elements in the matrix:
  • For each rotten orange (denoted by the current time in the time-stamped matrix), it tries to rot adjacent fresh oranges using the defined moves.
  • If a fresh orange is rotted, it updates its value to the current time plus one, marking the time at which it starts rotting.
  • It continues this process until no more fresh oranges can be rotted in a pass.
• In the main part of the function, a time_counter starts at 2 (to account for the initial state as time 2 after the initial time 1 which is default for fresh oranges).
• The loop keeps running the spreadRotten function and incrementing the time_counter until no more rotting occurs.
• After rotting stops, the code checks if there are still fresh oranges left (denoted by 1 in the matrix). If any are found, it returns -1, indicating not all oranges can be rotted.
• If all oranges have rotten successfully, the function returns the total time taken (time_counter - 2 to adjust for the initial start at 2) which represents minutes passed.

The approach leverages simulation with a time-stamped matrix and checks adjacency via coordinate manipulation. This ensures a comprehensive spread of the rot while efficiently tracking the process time. It returns either the total minutes required for all oranges to rot or -1 if it's impossible.