Dada una array arr[][] , que consta de solo 0, 1 y 2, que representa una sala vacía , un paciente no infectado y un paciente infectado, respectivamente. En una unidad de tiempo, una persona infectada en el índice (i, j) puede infectar a una persona no infectada adyacente, es decir, en el índice (i – 1, j) , (i + 1, j) , (i, j – 1 ) y (i, j + 1) . La tarea es encontrar la cantidad mínima de tiempo necesaria para infectar a todos los pacientes. Si es imposible infectar a todos los pacientes, imprima “-1” .
Ejemplos:
Entrada: arr[][] = {{2, 1, 0, 2, 1}, {1, 0, 1, 2, 1}, {1, 0, 0, 2, 1}}
Salida: 2
Explicación:
En el momento t = 1: los pacientes en las posiciones {0, 0}, {0, 3}, {1, 3} y {2, 3} infectarán al paciente en {{0, 1}, {1, 0}, {0, 4}, {1, 2}, {1, 4}, {2, 4}} durante la primera unidad de tiempo.
En el momento t = 2: el paciente en {1, 0} se infectará e infectará al paciente en {2, 0}.Después de los intervalos de tiempo anteriores, todos los pacientes no infectados están infectados. Por lo tanto, la cantidad total de tiempo requerido es 2.
Entrada: arr[][] = {{2, 1, 0, 2, 1}, {0, 0, 1, 2, 1}, {1, 0, 0, 2, 1}}
Salida: -1
Enfoque: El problema dado se puede resolver usando BFS Traversal en la array 2D . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array 2D , digamos timeofinfection[][] con -1 , de modo que timeofinfection[i][j] almacene la hora en que el paciente en el índice (i, j) estuvo infectado.
- Inicialice una cola para almacenar índices de pacientes infectados y su tiempo de infección.
- Recorra la array dada arr[][] y realice las siguientes operaciones:
- Si el valor en la celda (i, j) es 2 , empuje esa celda a la cola con el tiempo de infección como 0 , es decir, {i, j, 0} .
- Iterar hasta que la cola no esté vacía y realizar los siguientes pasos:
- Extraiga el elemento frontal de la cola y guárdelo en una variable, digamos current .
- Desde la celda reventada actual (i, j) , si la celda adyacente tiene una persona infectada que no ha sido visitada, luego empuje el índice de la celda adyacente con (1 + tiempo de infección de la celda reventada actual) en la cola.
- Después de completar los pasos anteriores, si se visitan todas las personas infectadas , es decir, el tiempo de infección de todas las personas infectadas no es negativo, imprima el elemento máximo presente en la array timeofinfection[][] como la unidad máxima de tiempo requerida para infectar a todos los pacientes.
- De lo contrario, imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Direction arrays vector<pair<int, int> > direction = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 } }; // Function to find the maximum time // required for all patients to get infected int maximumTime(vector<vector<int> > arr) { // Stores the number of rows int n = arr.size(); // Stores the number of columns int m = arr[0].size(); // Stores the time of infection // of the patient at index (i, j) int timeofinfection[n][m]; // Stores index and time of // infection of infected persons queue<pair<pair<int, int>, int> > q; // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Set the cell as unvisited timeofinfection[i][j] = -1; // If the current patient // is already infected if (arr[i][j] == 2) { // Push the index and time of // infection of current patient q.push({ { i, j }, 0 }); timeofinfection[i][j] = 0; } } } // Iterate until queue becomes empty while (!q.empty()) { // Stores the front element of queue pair<pair<int, int>, int> current = q.front(); // Pop out the front element q.pop(); // Check for all four // adjacent indices for (auto it : direction) { // Find the index of the // adjacent cell int i = current.first.first + it.first; int j = current.first.second + it.second; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || timeofinfection[i][j] != -1) { // Continue to the next // neighbouring cell continue; } // Push the infected // neighbour into queue q.push({ { i, j }, current.second + 1 }); timeofinfection[i][j] = current.second + 1; } } // Stores the maximum time int maxi = INT_MIN; // Stores if any uninfected // patient exists or not int flag = 0; // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If no patient is // present at index (i, j) if (arr[i][j] != 1) continue; // If an uninfected patient // is present at index (i, j) if (arr[i][j] == 1 && timeofinfection[i][j] == -1) { // Set flag as true flag = 1; break; } // Update the maximum time of infection maxi = max(maxi, timeofinfection[i][j]); } } // If an uninfected patient is present if (flag) return -1; // Return the final result return maxi; } // Driver Code int main() { vector<vector<int> > arr = { { 2, 1, 0, 2, 1 }, { 1, 0, 1, 2, 1 }, { 1, 0, 0, 2, 1 } }; cout << maximumTime(arr); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { static class pair { int first, second, third; pair(int first,int second,int third) { this.first = first; this.second = second; this.third = third; } } // Direction arrays static int[][] direction = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 } }; // Function to find the maximum time // required for all patients to get infected static int maximumTime(int[][] arr) { // Stores the number of rows int n = arr.length; // Stores the number of columns int m = arr[0].length; // Stores the time of infection // of the patient at index (i, j) int[][] timeofinfection = new int[n][m]; // Stores index and time of // infection of infected persons Queue<pair> q = new LinkedList<>(); // Traverse the matrix for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { // Set the cell as unvisited timeofinfection[i][j] = -1; // If the current patient // is already infected if (arr[i][j] == 2) { // Push the index and time of // infection of current patient q.add(new pair(i, j, 0)); timeofinfection[i][j] = 0; } } } // Iterate until queue becomes empty while (!q.isEmpty()) { // Stores the front element of queue pair current = q.peek(); // Pop out the front element q.poll(); // Check for all four // adjacent indices for(int[] it : direction) { // Find the index of the // adjacent cell int i = current.first + it[0]; int j = current.second + it[1]; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || timeofinfection[i][j] != -1) { // Continue to the next // neighbouring cell continue; } // Push the infected // neighbour into queue q.add(new pair(i, j , current.second + 1 )); timeofinfection[i][j] = current.third + 1; } } // Stores the maximum time int maxi = Integer.MIN_VALUE; // Stores if any uninfected // patient exists or not int flag = 0; // Traverse the matrix for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { // If no patient is // present at index (i, j) if (arr[i][j] != 1) continue; // If an uninfected patient // is present at index (i, j) if (arr[i][j] == 1 && timeofinfection[i][j] == -1) { // Set flag as true flag = 1; break; } // Update the maximum time of infection maxi = Math.max(maxi, timeofinfection[i][j]); } } // If an uninfected patient is present if (flag == 1) return -1; // Return the final result return maxi; } // Driver code public static void main(String[] args) { int[][] arr = { { 2, 1, 0, 2, 1 }, { 1, 0, 1, 2, 1 }, { 1, 0, 0, 2, 1 } }; System.out.print(maximumTime(arr)); } } // This code is contributed by offbeat
Javascript
<script> // JavaScript program for the above approach // Direction arrays var direction = [ [ 1, 0 ], [ 0, -1 ], [ -1, 0 ], [ 0, 1 ] ]; // Function to find the maximum time // required for all patients to get infected function maximumTime(arr) { // Stores the number of rows var n = arr.length; // Stores the number of columns var m = arr[0].length; // Stores the time of infection // of the patient at index (i, j) var timeofinfection = Array.from(Array(n), ()=>Array(m)); // Stores index and time of // infection of infected persons var q = []; // Traverse the matrix for (var i = 0; i < n; i++) { for (var j = 0; j < m; j++) { // Set the cell as unvisited timeofinfection[i][j] = -1; // If the current patient // is already infected if (arr[i][j] == 2) { // Push the index and time of // infection of current patient q.push([ [ i, j ], 0 ]); timeofinfection[i][j] = 0; } } } // Iterate until queue becomes empty while (q.length!=0) { // Stores the front element of queue var current = q[0]; // Pop out the front element q.shift(); // Check for all four // adjacent indices for(var it of direction) { // Find the index of the // adjacent cell var i = current[0][0] + it[0]; var j = current[0][1] + it[1]; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || timeofinfection[i][j] != -1) { // Continue to the next // neighbouring cell continue; } // Push the infected // neighbour into queue q.push([[i, j], current[1] + 1 ]); timeofinfection[i][j] = current[1] + 1; } } // Stores the maximum time var maxi = -1000000000; // Stores if any uninfected // patient exists or not var flag = 0; // Traverse the matrix for (var i = 0; i < n; i++) { for (var j = 0; j < m; j++) { // If no patient is // present at index (i, j) if (arr[i][j] != 1) continue; // If an uninfected patient // is present at index (i, j) if (arr[i][j] == 1 && timeofinfection[i][j] == -1) { // Set flag as true flag = 1; break; } // Update the maximum time of infection maxi = Math.max(maxi, timeofinfection[i][j]); } } // If an uninfected patient is present if (flag) return -1; // Return the final result return maxi; } // Driver Code var arr = [ [ 2, 1, 0, 2, 1 ], [ 1, 0, 1, 2, 1 ], [ 1, 0, 0, 2, 1 ] ]; document.write( maximumTime(arr)); </script>
Python
# function to traverse to nearby possible directions def bfs(i, j, mat, time): # marking position as visited mat[i][j] = 0 # stack to store positions that got infected in one unit time stack = [] # direction arrays row = [-1, 0, 0, 1] col = [0, -1, 1, 0] # traversing to nearby uninfected beds for k in range(4): x = i+row[k] y = j+col[k] if x >= 0 and x < r and y >= 0 and y < c and mat[x][y] == 1: mat[x][y] = 0 stack.append((x, y)) # storing the time at which the patient got infected time[x][y] = time[i][j]+1 return stack # function to calculate maximum time def maxTime(hospital): # array to store the time at which the patients got infected time = [[0 for i in range(c)] for j in range(r)] # to store newly infected ones que = [] # initial run for i in range(r): for j in range(c): if hospital[i][j] == 2: que += bfs(i, j, hospital, time) # iterate till every infected patient has done spreading while(len(que) != 0): for x, y in que: temp = bfs(x, y, hospital, time) que = temp # finally calculating maximum time res = 0 for i in range(r): for j in range(c): # checking if there is any uninfected person if hospital[i][j] == 1: return -1 res = max(res, time[i][j]) return res # Driver Code Starts hospital = [[2, 1, 0, 2, 1], [1, 0, 1, 2, 1], [1, 0, 0, 2, 1]] r = len(hospital) c = len(hospital[0]) print(maxTime(hospital)) # Driver Code Ends
2
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)
Enfoque 2 : utiliza la misma técnica transversal de BFS, pero en lugar de utilizar una array de números enteros para realizar un seguimiento de si todos los pacientes están infectados, utiliza un único número entero que reduce el consumo de espacio general y la sobrecarga de realizar una comprobación adicional para los pacientes no infectados.
La idea básica es que almacenaremos el recuento de personas no infectadas al principio y, a medida que un individuo se infecte, disminuiremos este recuento. Esto eliminará la sobrecarga de verificar si hay personas no infectadas al final. Y la hora a la que se infectó la última persona será nuestra respuesta final.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Direction arrays vector<pair<int, int> > direction = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 } }; // Function to find the maximum time // required for all patients to get infected int maximumTime(vector<vector<int> > arr) { // Stores the number of rows int n = arr.size(); // Stores the number of columns int m = arr[0].size(); // Stores whether particular index(i, j) // is visited or not vector<vector<bool>> visited(n,vector<bool>(m,0)); // Stores index and time of // infection of infected persons queue<pair<pair<int, int>, int> > q; //Stores uninfected patients count int uninfected_count=0; //Stores time at which last person got infected int time = 0; // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If the current patient // is already infected if (arr[i][j] == 2) { // Push the index of current patient // and mark it as visited q.push({ { i, j }, 0 }); visited[i][j] = 1; } //If current patient is uninfected //increment uninfected count if(arr[i][j] == 1){ uninfected_count++; } } } // Iterate until queue becomes empty while (!q.empty()) { // Stores the front element of queue pair<pair<int, int>, int> current = q.front(); time = current.second; // Pop out the front element q.pop(); // Check for all four // adjacent indices for (auto it : direction) { // Find the index of the // adjacent cell int i = current.first.first + it.first; int j = current.first.second + it.second; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || visited[i][j] != 0) { // Continue to the next // neighbouring cell continue; } // Push the infected // neighbour into queue q.push({ { i, j }, time + 1 }); visited[i][j] = 1; uninfected_count--; } } // If an uninfected patient is present if (uninfected_count != 0) return -1; // Return the final result return time; } // Driver Code int main() { vector<vector<int> > arr = { { 2, 1, 0, 2, 1 }, { 1, 0, 1, 2, 1 }, { 1, 0, 0, 2, 1 } }; cout << maximumTime(arr); return 0; } // Contributed By Devendra Kolhe
Java
// Java program for the above approach import java.util.*; public class GFG{ static class pair { int first, second, third; pair(int first,int second,int third) { this.first = first; this.second = second; this.third = third; } } // Direction arrays static int direction[][] = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 } }; // Function to find the maximum time // required for all patients to get infected static int maximumTime(int arr[][]) { // Stores the number of rows int n = arr.length; // Stores the number of columns int m = arr[0].length; // Stores whether particular index(i, j) // is visited or not boolean visited[][] = new boolean[n][m]; // Stores index and time of // infection of infected persons Queue<pair> q = new LinkedList<>(); //Stores uninfected patients count int uninfected_count=0; //Stores time at which last person got infected int time = 0; // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If the current patient // is already infected if (arr[i][j] == 2) { // Push the index of current patient // and mark it as visited q.add( new pair(i, j, 0 )); visited[i][j] = true; } //If current patient is uninfected //increment uninfected count if(arr[i][j] == 1){ uninfected_count++; } } } // Iterate until queue becomes empty while (!q.isEmpty()) { // Stores the front element of queue pair current = q.peek(); time = current.third; // Pop out the front element q.poll(); // Check for all four // adjacent indices for (int[] it : direction) { // Find the index of the // adjacent cell int i = current.first + it[0]; int j = current.second + it[1]; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || visited[i][j]) { // Continue to the next // neighbouring cell continue; } // Push the infected // neighbour into queue q.add( new pair( i, j, time + 1 )); visited[i][j] = true; uninfected_count--; } } // If an uninfected patient is present if (uninfected_count != 0) return -1; // Return the final result return time; } // Driver Code public static void main(String args[]) { int arr[][] = { { 2, 1, 0, 2, 1 }, { 1, 0, 1, 2, 1 }, { 1, 0, 0, 2, 1 } }; System.out.println(maximumTime(arr)); } } // This code is contributed by adityapande88.
2
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