Tiempo máximo requerido para que todos los pacientes se infecten

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *