Dada una array de dimensión m*n donde cada celda de la array puede tener valores 0, 1 o 2 lo que tiene el siguiente significado:
0: Empty cell 1: Cells have fresh oranges 2: Cells have rotten oranges
Determine cuál es el tiempo mínimo necesario para que todas las naranjas se pudran. Una naranja podrida en el índice [i,j] puede pudrir otra naranja fresca en los índices [i-1,j], [i+1,j], [i,j-1], [i,j+1] (hasta , abajo, izquierda y derecha). Si es imposible pudrir todas las naranjas, simplemente devuelva -1.
Ejemplos:
Input: arr[][C] = { {2, 1, 0, 2, 1},
{1, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
Output:
All oranges can become rotten in 2-time frames.
Explanation:
At 0th time frame:
{2, 1, 0, 2, 1}
{1, 0, 1, 2, 1}
{1, 0, 0, 2, 1}
At 1st time frame:
{2, 2, 0, 2, 2}
{2, 0, 2, 2, 2}
{1, 0, 0, 2, 2}
At 2nd time frame:
{2, 2, 0, 2, 2}
{2, 0, 2, 2, 2}
{2, 0, 0, 2, 2}
Input: arr[][C] = { {2, 1, 0, 2, 1},
{0, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
Output:
All oranges cannot be rotten.
Explanation:
At 0th time frame:
{2, 1, 0, 2, 1}
{0, 0, 1, 2, 1}
{1, 0, 0, 2, 1}
At 1st time frame:
{2, 2, 0, 2, 2}
{0, 0, 2, 2, 2}
{1, 0, 0, 2, 2}
At 2nd time frame:
{2, 2, 0, 2, 2}
{0, 0, 2, 2, 2}
{1, 0, 0, 2, 2}
...
The 1 at the bottom left corner of the matrix is never rotten.
Solución ingenua:
- Enfoque: La idea es muy básica. Atraviesa todas las naranjas en múltiples rondas. En cada ronda, pudra las naranjas a la posición adyacente de las naranjas que se pudrieron en la última ronda.
- Algoritmo:
- Crear una variable no = 2 y cambiada = falsa
- Ejecute un ciclo hasta que no haya ninguna celda de la array que se cambie en una iteración.
- Ejecute un bucle anidado y recorra la array. Si el elemento de la array es igual a no , asigne los elementos adyacentes a no + 1 si el valor del elemento adyacente es igual a 1, es decir, no corrupto, y actualice cambiado a verdadero.
- Recorra la array y verifique si hay alguna celda que sea 1. Si 1 está presente, devuelva -1
- De lo contrario, devuelva no – 2
- Implementación:
C++14
// C++ program to rot all oranges when u can move
// in all the four direction from a rotten orange
#include <bits/stdc++.h>
using namespace std;
const int R = 3;
const int C = 5;
// Check if i, j is under the array limits of row and column
bool issafe(int i, int j)
{
if (i >= 0 && i < R && j >= 0 && j < C)
return true;
return false;
}
int rotOranges(int v[R][C])
{
bool changed = false;
int no = 2;
while (true) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// Rot all other oranges present at
// (i+1, j), (i, j-1), (i, j+1), (i-1, j)
if (v[i][j] == no) {
if (issafe(i + 1, j) && v[i + 1][j] == 1) {
v[i + 1][j] = v[i][j] + 1;
changed = true;
}
if (issafe(i, j + 1) && v[i][j + 1] == 1) {
v[i][j + 1] = v[i][j] + 1;
changed = true;
}
if (issafe(i - 1, j) && v[i - 1][j] == 1) {
v[i - 1][j] = v[i][j] + 1;
changed = true;
}
if (issafe(i, j - 1) && v[i][j - 1] == 1) {
v[i][j - 1] = v[i][j] + 1;
changed = true;
}
}
}
}
// if no rotten orange found it means all
// oranges rottened now
if (!changed)
break;
changed = false;
no++;
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// if any orange is found to be
// not rotten then ans is not possible
if (v[i][j] == 1)
return -1;
}
}
// Because initial value for a rotten
// orange was 2
return no - 2;
}
// Driver function
int main()
{
int v[R][C] = { { 2, 1, 0, 2, 1 },
{ 1, 0, 1, 2, 1 },
{ 1, 0, 0, 2, 1 } };
cout << "Max time incurred: " << rotOranges(v);
return 0;
}
Java
// Java program to rot all oranges when u can move
// in all the four direction from a rotten orange
class GFG{
static int R = 3;
static int C = 5;
// Check if i, j is under the array
// limits of row and column
static boolean issafe(int i, int j)
{
if (i >= 0 && i < R &&
j >= 0 && j < C)
return true;
return false;
}
static int rotOranges(int v[][])
{
boolean changed = false;
int no = 2;
while (true)
{
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
// Rot all other oranges present at
// (i+1, j), (i, j-1), (i, j+1), (i-1, j)
if (v[i][j] == no)
{
if (issafe(i + 1, j) &&
v[i + 1][j] == 1)
{
v[i + 1][j] = v[i][j] + 1;
changed = true;
}
if (issafe(i, j + 1) &&
v[i][j + 1] == 1)
{
v[i][j + 1] = v[i][j] + 1;
changed = true;
}
if (issafe(i - 1, j) &&
v[i - 1][j] == 1)
{
v[i - 1][j] = v[i][j] + 1;
changed = true;
}
if (issafe(i, j - 1) &&
v[i][j - 1] == 1)
{
v[i][j - 1] = v[i][j] + 1;
changed = true;
}
}
}
}
// If no rotten orange found it means all
// oranges rottened now
if (!changed)
break;
changed = false;
no++;
}
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
// If any orange is found to be
// not rotten then ans is not possible
if (v[i][j] == 1)
return -1;
}
}
// Because initial value for a rotten
// orange was 2
return no - 2;
}
// Driver Code
public static void main(String[] args)
{
int v[][] = { { 2, 1, 0, 2, 1 },
{ 1, 0, 1, 2, 1 },
{ 1, 0, 0, 2, 1 } };
System.out.println("Max time incurred: " +
rotOranges(v));
}
}
// This code is contributed by divyesh072019
Python3
# Python3 program to rot all
# oranges when u can move
# in all the four direction
# from a rotten orange
R = 3
C = 5
# Check if i, j is under the
# array limits of row and
# column
def issafe(i, j):
if (i >= 0 and i < R and
j >= 0 and j < C):
return True
return False
def rotOranges(v):
changed = False
no = 2
while (True):
for i in range(R):
for j in range(C):
# Rot all other oranges
# present at (i+1, j),
# (i, j-1), (i, j+1),
# (i-1, j)
if (v[i][j] == no):
if (issafe(i + 1, j) and
v[i + 1][j] == 1):
v[i + 1][j] = v[i][j] + 1
changed = True
if (issafe(i, j + 1) and
v[i][j + 1] == 1):
v[i][j + 1] = v[i][j] + 1
changed = True
if (issafe(i - 1, j) and
v[i - 1][j] == 1):
v[i - 1][j] = v[i][j] + 1
changed = True
if (issafe(i, j - 1) and
v[i][j - 1] == 1):
v[i][j - 1] = v[i][j] + 1
changed = True
# if no rotten orange found
# it means all oranges rottened
# now
if (not changed):
break
changed = False
no += 1
for i in range(R):
for j in range(C):
# if any orange is found
# to be not rotten then
# ans is not possible
if (v[i][j] == 1):
return -1
# Because initial value
# for a rotten orange was 2
return no - 2
# Driver function
if __name__ == "__main__":
v = [[2, 1, 0, 2, 1],
[1, 0, 1, 2, 1],
[1, 0, 0, 2, 1]]
print("Max time incurred: ",
rotOranges(v))
# This code is contributed by Chitranayal
C#
// C# program to rot all oranges when u can move
// in all the four direction from a rotten orange
using System;
class GFG {
static int R = 3;
static int C = 5;
// Check if i, j is under the array
// limits of row and column
static bool issafe(int i, int j)
{
if (i >= 0 && i < R && j >= 0 && j < C)
return true;
return false;
}
static int rotOranges(int[,] v)
{
bool changed = false;
int no = 2;
while (true) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// Rot all other oranges present at
// (i+1, j), (i, j-1), (i, j+1), (i-1, j)
if (v[i, j] == no) {
if (issafe(i + 1, j) && v[i + 1, j] == 1) {
v[i + 1, j] = v[i, j] + 1;
changed = true;
}
if (issafe(i, j + 1) && v[i, j + 1] == 1) {
v[i, j + 1] = v[i, j] + 1;
changed = true;
}
if (issafe(i - 1, j) && v[i - 1, j] == 1) {
v[i - 1, j] = v[i, j] + 1;
changed = true;
}
if (issafe(i, j - 1) && v[i, j - 1] == 1) {
v[i, j - 1] = v[i, j] + 1;
changed = true;
}
}
}
}
// if no rotten orange found it means all
// oranges rottened now
if (!changed)
break;
changed = false;
no++;
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// if any orange is found to be
// not rotten then ans is not possible
if (v[i, j] == 1)
return -1;
}
}
// Because initial value for a rotten
// orange was 2
return no - 2;
}
static void Main() {
int[ , ] v = { { 2, 1, 0, 2, 1 },
{ 1, 0, 1, 2, 1 },
{ 1, 0, 0, 2, 1 } };
Console.Write("Max time incurred: " + rotOranges(v));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program to rot all oranges when u can move
// in all the four direction from a rotten orange
let R = 3;
let C = 5;
// Check if i, j is under the array limits of row and column
function issafe(i, j)
{
if (i >= 0 && i < R && j >= 0 && j < C)
return true;
return false;
}
function rotOranges(v)
{
let changed = false;
let no = 2;
while (true) {
for (let i = 0; i < R; i++) {
for (let j = 0; j < C; j++) {
// Rot all other oranges present at
// (i+1, j), (i, j-1), (i, j+1), (i-1, j)
if (v[i][j] == no) {
if (issafe(i + 1, j) && v[i + 1][j] == 1) {
v[i + 1][j] = v[i][j] + 1;
changed = true;
}
if (issafe(i, j + 1) && v[i][j + 1] == 1) {
v[i][j + 1] = v[i][j] + 1;
changed = true;
}
if (issafe(i - 1, j) && v[i - 1][j] == 1) {
v[i - 1][j] = v[i][j] + 1;
changed = true;
}
if (issafe(i, j - 1) && v[i][j - 1] == 1) {
v[i][j - 1] = v[i][j] + 1;
changed = true;
}
}
}
}
// if no rotten orange found it means all
// oranges rottened now
if (!changed)
break;
changed = false;
no++;
}
for (let i = 0; i < R; i++) {
for (let j = 0; j < C; j++) {
// if any orange is found to be
// not rotten then ans is not possible
if (v[i][j] == 1)
return -1;
}
}
// Because initial value for a rotten
// orange was 2
return no - 2;
}
// Driver code
let v = [ [ 2, 1, 0, 2, 1 ],
[ 1, 0, 1, 2, 1 ],
[ 1, 0, 0, 2, 1 ] ];
document.write("Max time incurred: " + rotOranges(v));
// This code is contributed by mukesh07.
</script>
Producción:
Max time incurred: 2
- Análisis de Complejidad:
- Complejidad temporal : O((R*C) * (R *C)).
La array debe atravesarse una y otra vez hasta que no haya cambios en la array, eso puede ocurrir max(R *C)/2 veces. Entonces la complejidad del tiempo es O((R * C) * (R *C)). - Complejidad espacial: O(1).
No se requiere espacio adicional.
- Complejidad temporal : O((R*C) * (R *C)).
Solución eficiente
- Enfoque: La idea es utilizar Breadth First Search . La condición de las naranjas que se pudren es cuando entran en contacto con otras naranjas podridas. Esto es similar a la búsqueda primero en amplitud donde el gráfico se divide en capas o círculos y la búsqueda se realiza desde las capas más bajas o más cercanas a las capas más profundas o más altas. En el enfoque anterior, la idea se basaba en BFS pero la implementación era deficiente e ineficiente. Para encontrar los elementos cuyos valores son no , se tuvo que recorrer toda la array. De modo que el tiempo se puede reducir utilizando este enfoque eficiente de BFS.
- Algoritmo:
- Cree una cola vacía Q.
- Encuentre todas las naranjas podridas y póngalas en cola en Q. Además, ponga en cola un delimitador para indicar el comienzo del siguiente período de tiempo.
- Ejecutar un ciclo mientras Q no está vacío
- Hacer seguimiento mientras no se alcanza el delimitador en Q
- Retire una naranja de la cola, pudra todas las naranjas adyacentes. Mientras pudre el adyacente, asegúrese de que el marco de tiempo se incremente solo una vez. Y el marco de tiempo no se incrementa si no hay naranjas adyacentes.
- Retire de la cola el delimitador antiguo y ponga en cola un delimitador nuevo. Las naranjas podridas en el marco de tiempo anterior se encuentran entre los dos delimitadores.
- Cree una cola vacía Q.
- Ejecución en seco del enfoque anterior:
- Implementación:
C++
// C++ program to find minimum time required to make all
// oranges rotten
#include<bits/stdc++.h>
#define R 3
#define C 5
using namespace std;
// function to check whether a cell is valid / invalid
bool isvalid(int i, int j)
{
return (i >= 0 && j >= 0 && i < R && j < C);
}
// structure for storing coordinates of the cell
struct ele {
int x, y;
};
// Function to check whether the cell is delimiter
// which is (-1, -1)
bool isdelim(ele temp)
{
return (temp.x == -1 && temp.y == -1);
}
// Function to check whether there is still a fresh
// orange remaining
bool checkall(int arr[][C])
{
for (int i=0; i<R; i++)
for (int j=0; j<C; j++)
if (arr[i][j] == 1)
return true;
return false;
}
// This function finds if it is possible to rot all oranges or not.
// If possible, then it returns minimum time required to rot all,
// otherwise returns -1
int rotOranges(int arr[][C])
{
// Create a queue of cells
queue<ele> Q;
ele temp;
int ans = 0;
// Store all the cells having rotten orange in first time frame
for (int i=0; i<R; i++)
{
for (int j=0; j<C; j++)
{
if (arr[i][j] == 2)
{
temp.x = i;
temp.y = j;
Q.push(temp);
}
}
}
// Separate these rotten oranges from the oranges which will rotten
// due the oranges in first time frame using delimiter which is (-1, -1)
temp.x = -1;
temp.y = -1;
Q.push(temp);
// Process the grid while there are rotten oranges in the Queue
while (!Q.empty())
{
// This flag is used to determine whether even a single fresh
// orange gets rotten due to rotten oranges in current time
// frame so we can increase the count of the required time.
bool flag = false;
// Process all the rotten oranges in current time frame.
while (!isdelim(Q.front()))
{
temp = Q.front();
// Check right adjacent cell that if it can be rotten
if (isvalid(temp.x+1, temp.y) && arr[temp.x+1][temp.y] == 1)
{
// if this is the first orange to get rotten, increase
// count and set the flag.
if (!flag) ans++, flag = true;
// Make the orange rotten
arr[temp.x+1][temp.y] = 2;
// push the adjacent orange to Queue
temp.x++;
Q.push(temp);
temp.x--; // Move back to current cell
}
// Check left adjacent cell that if it can be rotten
if (isvalid(temp.x-1, temp.y) && arr[temp.x-1][temp.y] == 1) {
if (!flag) ans++, flag = true;
arr[temp.x-1][temp.y] = 2;
temp.x--;
Q.push(temp); // push this cell to Queue
temp.x++;
}
// Check top adjacent cell that if it can be rotten
if (isvalid(temp.x, temp.y+1) && arr[temp.x][temp.y+1] == 1) {
if (!flag) ans++, flag = true;
arr[temp.x][temp.y+1] = 2;
temp.y++;
Q.push(temp); // Push this cell to Queue
temp.y--;
}
// Check bottom adjacent cell if it can be rotten
if (isvalid(temp.x, temp.y-1) && arr[temp.x][temp.y-1] == 1) {
if (!flag) ans++, flag = true;
arr[temp.x][temp.y-1] = 2;
temp.y--;
Q.push(temp); // push this cell to Queue
}
Q.pop();
}
// Pop the delimiter
Q.pop();
// If oranges were rotten in current frame than separate the
// rotten oranges using delimiter for the next frame for processing.
if (!Q.empty()) {
temp.x = -1;
temp.y = -1;
Q.push(temp);
}
// If Queue was empty than no rotten oranges left to process so exit
}
// Return -1 if all arranges could not rot, otherwise return ans.
return (checkall(arr))? -1: ans;
}
// Driver program
int main()
{
int arr[][C] = { {2, 1, 0, 2, 1},
{1, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
int ans = rotOranges(arr);
if (ans == -1)
cout << "All oranges cannot rotn";
else
cout << "Time required for all oranges to rot => " << ans << endl;
return 0;
}
Java
//Java program to find minimum time required to make all
//oranges rotten
import java.util.LinkedList;
import java.util.Queue;
public class RotOrange
{
public final static int R = 3;
public final static int C = 5;
// structure for storing coordinates of the cell
static class Ele
{
int x = 0;
int y = 0;
Ele(int x,int y)
{
this.x = x;
this.y = y;
}
}
// function to check whether a cell is valid / invalid
static boolean isValid(int i, int j)
{
return (i >= 0 && j >= 0 && i < R && j < C);
}
// Function to check whether the cell is delimiter
// which is (-1, -1)
static boolean isDelim(Ele temp)
{
return (temp.x == -1 && temp.y == -1);
}
// Function to check whether there is still a fresh
// orange remaining
static boolean checkAll(int arr[][])
{
for (int i=0; i<R; i++)
for (int j=0; j<C; j++)
if (arr[i][j] == 1)
return true;
return false;
}
// This function finds if it is possible to rot all oranges or not.
// If possible, then it returns minimum time required to rot all,
// otherwise returns -1
static int rotOranges(int arr[][])
{
// Create a queue of cells
Queue<Ele> Q=new LinkedList<>();
Ele temp;
int ans = 0;
// Store all the cells having rotten orange in first time frame
for (int i=0; i < R; i++)
for (int j=0; j < C; j++)
if (arr[i][j] == 2)
Q.add(new Ele(i,j));
// Separate these rotten oranges from the oranges which will rotten
// due the oranges in first time frame using delimiter which is (-1, -1)
Q.add(new Ele(-1,-1));
// Process the grid while there are rotten oranges in the Queue
while(!Q.isEmpty())
{
// This flag is used to determine whether even a single fresh
// orange gets rotten due to rotten oranges in the current time
// frame so we can increase the count of the required time.
boolean flag = false;
// Process all the rotten oranges in current time frame.
while(!isDelim(Q.peek()))
{
temp = Q.peek();
// Check right adjacent cell that if it can be rotten
if(isValid(temp.x+1, temp.y) && arr[temp.x+1][temp.y] == 1)
{
if(!flag)
{
// if this is the first orange to get rotten, increase
// count and set the flag.
ans++;
flag = true;
}
// Make the orange rotten
arr[temp.x+1][temp.y] = 2;
// push the adjacent orange to Queue
temp.x++;
Q.add(new Ele(temp.x,temp.y));
// Move back to current cell
temp.x--;
}
// Check left adjacent cell that if it can be rotten
if (isValid(temp.x-1, temp.y) && arr[temp.x-1][temp.y] == 1)
{
if (!flag)
{
ans++;
flag = true;
}
arr[temp.x-1][temp.y] = 2;
temp.x--;
Q.add(new Ele(temp.x,temp.y)); // push this cell to Queue
temp.x++;
}
// Check top adjacent cell that if it can be rotten
if (isValid(temp.x, temp.y+1) && arr[temp.x][temp.y+1] == 1) {
if(!flag)
{
ans++;
flag = true;
}
arr[temp.x][temp.y+1] = 2;
temp.y++;
Q.add(new Ele(temp.x,temp.y)); // Push this cell to Queue
temp.y--;
}
// Check bottom adjacent cell if it can be rotten
if (isValid(temp.x, temp.y-1) && arr[temp.x][temp.y-1] == 1)
{
if (!flag)
{
ans++;
flag = true;
}
arr[temp.x][temp.y-1] = 2;
temp.y--;
Q.add(new Ele(temp.x,temp.y)); // push this cell to Queue
}
Q.remove();
}
// Pop the delimiter
Q.remove();
// If oranges were rotten in current frame than separate the
// rotten oranges using delimiter for the next frame for processing.
if (!Q.isEmpty())
{
Q.add(new Ele(-1,-1));
}
// If Queue was empty than no rotten oranges left to process so exit
}
// Return -1 if all arranges could not rot, otherwise ans
return (checkAll(arr))? -1: ans;
}
// Driver program
public static void main(String[] args)
{
int arr[][] = { {2, 1, 0, 2, 1},
{1, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
int ans = rotOranges(arr);
if(ans == -1)
System.out.println("All oranges cannot rot");
else
System.out.println("Time required for all oranges to rot = " + ans);
}
}
//This code is contributed by Sumit Ghosh
Python3
# Python3 program to find minimum time required to make all
# oranges rotten
from collections import deque
# function to check whether a cell is valid / invalid
def isvalid(i, j):
return (i >= 0 and j >= 0 and i < 3 and j < 5)
# Function to check whether the cell is delimiter
# which is (-1, -1)
def isdelim(temp):
return (temp[0] == -1 and temp[1] == -1)
# Function to check whether there is still a fresh
# orange remaining
def checkall(arr):
for i in range(3):
for j in range(5):
if (arr[i][j] == 1):
return True
return False
# This function finds if it is
# possible to rot all oranges or not.
# If possible, then it returns
# minimum time required to rot all,
# otherwise returns -1
def rotOranges(arr):
# Create a queue of cells
Q = deque()
temp = [0, 0]
ans = 1
# Store all the cells having
# rotten orange in first time frame
for i in range(3):
for j in range(5):
if (arr[i][j] == 2):
temp[0]= i
temp[1] = j
Q.append([i, j])
# Separate these rotten oranges
# from the oranges which will rotten
# due the oranges in first time
# frame using delimiter which is (-1, -1)
temp[0] = -1
temp[1] = -1
Q.append([-1, -1])
# print(Q)
# Process the grid while there are
# rotten oranges in the Queue
while False:
# This flag is used to determine
# whether even a single fresh
# orange gets rotten due to rotten
# oranges in current time
# frame so we can increase
# the count of the required time.
flag = False
print(len(Q))
# Process all the rotten
# oranges in current time frame.
while not isdelim(Q[0]):
temp = Q[0]
print(len(Q))
# Check right adjacent cell that if it can be rotten
if (isvalid(temp[0] + 1, temp[1]) and arr[temp[0] + 1][temp[1]] == 1):
# if this is the first orange to get rotten, increase
# count and set the flag.
if (not flag):
ans, flag =ans + 1, True
# Make the orange rotten
arr[temp[0] + 1][temp[1]] = 2
# append the adjacent orange to Queue
temp[0] += 1
Q.append(temp)
temp[0] -= 1 # Move back to current cell
# Check left adjacent cell that if it can be rotten
if (isvalid(temp[0] - 1, temp[1]) and arr[temp[0] - 1][temp[1]] == 1):
if (not flag):
ans, flag =ans + 1, True
arr[temp[0] - 1][temp[1]] = 2
temp[0] -= 1
Q.append(temp) # append this cell to Queue
temp[0] += 1
# Check top adjacent cell that if it can be rotten
if (isvalid(temp[0], temp[1] + 1) and arr[temp[0]][temp[1] + 1] == 1):
if (not flag):
ans, flag = ans + 1, True
arr[temp[0]][temp[1] + 1] = 2
temp[1] += 1
Q.append(temp) # Push this cell to Queue
temp[1] -= 1
# Check bottom adjacent cell if it can be rotten
if (isvalid(temp[0], temp[1] - 1) and arr[temp[0]][temp[1] - 1] == 1):
if (not flag):
ans, flag = ans + 1, True
arr[temp[0]][temp[1] - 1] = 2
temp[1] -= 1
Q.append(temp) # append this cell to Queue
Q.popleft()
# Pop the delimiter
Q.popleft()
# If oranges were rotten in
# current frame than separate the
# rotten oranges using delimiter
# for the next frame for processing.
if (len(Q) == 0):
temp[0] = -1
temp[1] = -1
Q.append(temp)
# If Queue was empty than no rotten oranges left to process so exit
# Return -1 if all arranges could not rot, otherwise return ans.
return ans + 1 if(checkall(arr)) else -1
# Driver program
if __name__ == '__main__':
arr = [[2, 1, 0, 2, 1],
[1, 0, 1, 2, 1],
[1, 0, 0, 2, 1]]
ans = rotOranges(arr)
if (ans == -1):
print("All oranges cannot rotn")
else:
print("Time required for all oranges to rot => " , ans)
# This code is contributed by mohit kumar 29
C#
// C# program to find minimum time
// required to make all oranges rotten
using System;
using System.Collections.Generic;
class GFG
{
public const int R = 3;
public const int C = 5;
// structure for storing
// coordinates of the cell
public class Ele
{
public int x = 0;
public int y = 0;
public Ele(int x, int y)
{
this.x = x;
this.y = y;
}
}
// function to check whether a cell
// is valid / invalid
public static bool isValid(int i, int j)
{
return (i >= 0 && j >= 0 &&
i < R && j < C);
}
// Function to check whether the cell
// is delimiter which is (-1, -1)
public static bool isDelim(Ele temp)
{
return (temp.x == -1 && temp.y == -1);
}
// Function to check whether there
// is still a fresh orange remaining
public static bool checkAll(int[][] arr)
{
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
if (arr[i][j] == 1)
{
return true;
}
}
}
return false;
}
// This function finds if it is possible
// to rot all oranges or not. If possible,
// then it returns minimum time required
// to rot all, otherwise returns -1
public static int rotOranges(int[][] arr)
{
// Create a queue of cells
LinkedList<Ele> Q = new LinkedList<Ele>();
Ele temp;
int ans = 0;
// Store all the cells having rotten
// orange in first time frame
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
if (arr[i][j] == 2)
{
Q.AddLast(new Ele(i, j));
}
}
}
// Separate these rotten oranges from
// the oranges which will rotten
// due the oranges in first time frame
// using delimiter which is (-1, -1)
Q.AddLast(new Ele(-1,-1));
// Process the grid while there are
// rotten oranges in the Queue
while (Q.Count > 0)
{
// This flag is used to determine
// whether even a single fresh
// orange gets rotten due to rotten
// oranges in current time frame so
// we can increase the count of the
// required time.
bool flag = false;
// Process all the rotten oranges
// in current time frame.
while (!isDelim(Q.First.Value))
{
temp = Q.First.Value;
// Check right adjacent cell that
// if it can be rotten
if (isValid(temp.x + 1, temp.y) &&
arr[temp.x + 1][temp.y] == 1)
{
if (!flag)
{
// if this is the first orange
// to get rotten, increase
// count and set the flag.
ans++;
flag = true;
}
// Make the orange rotten
arr[temp.x + 1][temp.y] = 2;
// push the adjacent orange to Queue
temp.x++;
Q.AddLast(new Ele(temp.x,temp.y));
// Move back to current cell
temp.x--;
}
// Check left adjacent cell that
// if it can be rotten
if (isValid(temp.x - 1, temp.y) &&
arr[temp.x - 1][temp.y] == 1)
{
if (!flag)
{
ans++;
flag = true;
}
arr[temp.x - 1][temp.y] = 2;
temp.x--;
// push this cell to Queue
Q.AddLast(new Ele(temp.x,temp.y));
temp.x++;
}
// Check top adjacent cell that
// if it can be rotten
if (isValid(temp.x, temp.y + 1) &&
arr[temp.x][temp.y + 1] == 1)
{
if (!flag)
{
ans++;
flag = true;
}
arr[temp.x][temp.y + 1] = 2;
temp.y++;
// Push this cell to Queue
Q.AddLast(new Ele(temp.x,temp.y));
temp.y--;
}
// Check bottom adjacent cell
// if it can be rotten
if (isValid(temp.x, temp.y - 1) &&
arr[temp.x][temp.y - 1] == 1)
{
if (!flag)
{
ans++;
flag = true;
}
arr[temp.x][temp.y - 1] = 2;
temp.y--;
// push this cell to Queue
Q.AddLast(new Ele(temp.x,temp.y));
}
Q.RemoveFirst();
}
// Pop the delimiter
Q.RemoveFirst();
// If oranges were rotten in current
// frame than separate the rotten
// oranges using delimiter for the
// next frame for processing.
if (Q.Count > 0)
{
Q.AddLast(new Ele(-1,-1));
}
// If Queue was empty than no rotten
// oranges left to process so exit
}
// Return -1 if all arranges could
// not rot, otherwise ans
return (checkAll(arr)) ? -1: ans;
}
// Driver Code
public static void Main(string[] args)
{
int[][] arr = new int[][]
{
new int[] {2, 1, 0, 2, 1},
new int[] {1, 0, 1, 2, 1},
new int[] {1, 0, 0, 2, 1}
};
int ans = rotOranges(arr);
if (ans == -1)
{
Console.WriteLine("All oranges cannot rot");
}
else
{
Console.WriteLine("Time required for all " +
"oranges to rot => " + ans);
}
}
}
// This code is contributed by Shrikant13
Producción
Time required for all oranges to rot => 2
- Análisis de Complejidad:
- Complejidad temporal: O( R *C).
Cada elemento de la array se puede insertar en la cola solo una vez, por lo que el límite superior de la iteración es O(R*C), es decir, el número de elementos. Entonces la complejidad del tiempo es O(R *C). - Complejidad espacial: O(R*C).
Para almacenar los elementos en una cola se necesita un espacio O(R*C).
- Complejidad temporal: O( R *C).
Gracias a Gaurav Ahirwar por sugerir la solución anterior.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA