You are given a grid of oranges and a list of connection times between adjacent cells. Each cell contains one of the following values:
0: an empty cell1: a fresh orange2: a rotten orange
A rotten orange can make a connected fresh orange rotten, but each connection may take a different amount of time. A connection is given as "row1,col1,row2,col2,time", meaning the cell at [row1, col1] and the cell at [row2, col2] are connected, and rotting can spread across this connection in time minutes.
Since different connections may take different amounts of time, rotting should always use the earliest possible time at which each orange can become rotten.
Return the minimum time needed for all fresh oranges to become rotten. If at least one fresh orange can never become rotten, return -1.
If multiple rotten oranges can reach the same fresh orange, use the earliest possible rotting time. This makes the output deterministic.
Method Signature
int minTimeToRotAllOranges(List<String> grid, List<String> connections)
grid represents the orange grid. Each string is one row, with comma-separated cell values.connections contains connection information in the format "row1,col1,row2,col2,time".- The method returns the minimum number of minutes required to rot all fresh oranges.
Constraints
1 ≤ grid.size() ≤ 1,0001 ≤ number of columns in each row ≤ 1,000- All rows in
grid have the same number of columns.
grid[row][col] is one of 0, 1, or 20 ≤ connections.size() ≤ 1,000,000- Each connection string has the format
"row1,col1,row2,col2,time"
0 ≤ row1, row2 < grid.size()0 ≤ col1, col2 < number of columns1 ≤ time ≤ 1,000,000,000- The two cells in a connection are directly adjacent horizontally or vertically.
- Connections are bidirectional.
- A connection involving an empty cell does not spread rotting through that empty cell.
- The final answer will fit in a 32-bit signed integer.
Examples
Example 1
minTimeToRotAllOranges(grid = ["2,1,1", "0,1,0"], connections = ["0,0,0,1,4", "0,1,0,2,2", "0,1,1,1,3"])
Output: 7
Explanation: The orange at [0,1] rots after 4 minutes. Then [0,2] rots at time 6, and [1,1] rots at time 7. Therefore, all fresh oranges are rotten after 7 minutes.
Example 2
minTimeToRotAllOranges(grid = ["2,1", "1,1"], connections = ["0,0,0,1,5", "0,0,1,0,1", "1,0,1,1,3", "0,1,1,1,10"])
Output: 5
Explanation: The orange at [1,0] rots at time 1. Then [1,1] rots at time 4. The orange at [0,1] rots at time 5. At that time, every fresh orange has become rotten.
Example 3
minTimeToRotAllOranges(grid = ["2,1,0", "0,1,1"], connections = ["0,0,0,1,2", "1,1,1,2,3"])
Output: -1
Explanation: The fresh oranges at [1,1] and [1,2] cannot be reached from any initially rotten orange. Therefore, it is impossible to rot all fresh oranges.
Example 4
minTimeToRotAllOranges(grid = ["2,0,1"], connections = ["0,0,0,1,3", "0,1,0,2,4"])
Output: -1
Explanation: The connection from [0,0] to [0,1] involves an empty cell, so rotting cannot spread through it. The fresh orange at [0,2] can never become rotten.