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
Producción
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.
Producción
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