Horas mínimas que tardan los zombis en infectar a todos los humanos infectando solo hacia arriba, hacia la izquierda, hacia abajo y hacia la derecha

Dada una cuadrícula 2D , cada celda es un zombi 1 o un humano 0 . Los zombis pueden convertir a los seres humanos adyacentes en posición horizontal o vertical (arriba/abajo/izquierda/derecha) en zombis cada hora. La tarea es averiguar cuántas horas llevará infectar a todos los humanos. 

Ejemplos: 

Entrada: arr[][] = { { 0, 1, 0, 1 }, 
                          { 0, 0, 0, 0 }, 
                         { 0, 0, 0, 1 } };
Salida:   3
Explicación: En tiempo = 3 horas todos los humanos se convertirán en zombis.

Entrada:  arr[][] = {{ 0, 1, 0 }, 
                          { 0, 0, 0 }, 
                         { 0, 0, 0 }};
Salida: 3

Enfoque: este problema se puede resolver mediante el uso de BFS de múltiples fuentes . Siga los pasos a continuación para resolver el problema dado. 

• Debido a que todos los zombis se están expandiendo al mismo tiempo, se debe usar BFS de múltiples fuentes .
• Empuje inicialmente todas las posiciones de los zombis en la cola .
• Si bien la cola no está vacía, intente visitar las cuatro direcciones para cada zombi porque el efecto de cada zombi estará en las cuatro direcciones.
• Después de cada conjunto de zombis, aumente el tiempo en 1 .
• En Compruebe si queda alguna celda para ser humana, eso significa que inicialmente no había ningún zombi en la cuadrícula, así que devuelva -1 .
• De lo contrario, devuelva el tiempo total necesario para infectar a todos los humanos.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// To check if current coordinate
// lies inside the grid or not
bool isValid(int i, int j, int n, int m)
{
    if (i < n and i >= 0 and j < m and j >= 0)
        return 1;
    else
        return 0;
}
 
// Function to find out minimum time required
// to infect all humans into zombies
int zombieInfection(vector<vector<int> >& grid)
{
    // Queue to store coordinates for BFS
    queue<pair<int, int> > q;
 
    // Number of rows
    int n = grid.size();
 
    // Number of columns
    int m = grid[0].size();
 
    int cur = 0, next = 0;
 
    // Initially pushing coordinates of all the
    // zombies into the queue
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
 
            // If cell is zombie
            if (grid[i][j] == 1) {
                q.push({ i, j });
                cur++;
            }
        }
    }
 
    // To keep track of the time
    int t = 0;
 
    // While any zombie is left
    while (!q.empty()) {
        for (int i = 0; i < cur; i++) {
            auto use = q.front();
            q.pop();
            int x = use.first, y = use.second;
 
            // Checking for all the four directons
            // horizontally and vertically
            if (isValid(x + 1, y, n, m)
                and grid[x + 1][y] == 0) {
                grid[x + 1][y] = 1;
                q.push({ x + 1, y });
                next++;
            }
            if (isValid(x - 1, y, n, m)
                and grid[x - 1][y] == 0) {
                grid[x - 1][y] = 1;
                q.push({ x - 1, y });
                next++;
            }
            if (isValid(x, y + 1, n, m)
                and grid[x][y + 1] == 0) {
                grid[x][y + 1] = 1;
                q.push({ x, y + 1 });
                next++;
            }
            if (isValid(x, y - 1, n, m)
                and grid[x][y - 1] == 0) {
                grid[x][y - 1] = 1;
                q.push({ x, y - 1 });
                next++;
            }
        }
        if (next == 0)
            break;
        cur = next;
        next = 0;
 
        // Increment time
        t++;
    }
 
    // If no zombie was there in the grid
    // Then it is not possible to convert all
    // the humans to zombie so return -1
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (grid[i][j] == 0)
                return -1;
 
    // Return the total time elapsed
    return t;
}
 
// Driver Code
int main()
{
    int N = 3, M = 4;
 
    // Given grid
    vector<vector<int> > grid = { { 0, 1, 0, 1 },
                                  { 0, 0, 0, 0 },
                                  { 0, 0, 0, 1 } };
 
    // Function Call
    cout << zombieInfection(grid);
 
    return 0;
}

// Java program for above approach
import java.util.*;
class GFG {
 
    // To check if current coordinate
    // lies inside the grid or not
    static boolean isValid(int i, int j, int n, int m)
    {
        if (i < n && i >= 0 && j < m && j >= 0)
            return true;
        else
            return false;
    }
    static class pair {
        int first, second;
        public pair(int first, int second)
        {
            this.first = first;
            this.second = second;
        }
    }
 
    // Function to find out minimum time required
    // to infect all humans into zombies
    static int zombieInfection(int[][] grid)
    {
 
        // Queue to store coordinates for BFS
        Queue<pair> q = new LinkedList<GFG.pair>();
 
        // Number of rows
        int n = grid.length;
 
        // Number of columns
        int m = grid[0].length;
 
        int cur = 0, next = 0;
 
        // Initially pushing coordinates of all the
        // zombies into the queue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
 
                // If cell is zombie
                if (grid[i][j] == 1) {
                    q.add(new pair(i, j));
                    cur++;
                }
            }
        }
 
        // To keep track of the time
        int t = 0;
 
        // While any zombie is left
        while (!q.isEmpty()) {
            for (int i = 0; i < cur; i++) {
                pair use = q.peek();
                q.remove();
                int x = use.first, y = use.second;
 
                // Checking for all the four directons
                // horizontally and vertically
                if (isValid(x + 1, y, n, m)
                    && grid[x + 1][y] == 0) {
                    grid[x + 1][y] = 1;
                    q.add(new pair(x + 1, y));
                    next++;
                }
                if (isValid(x - 1, y, n, m)
                    && grid[x - 1][y] == 0) {
                    grid[x - 1][y] = 1;
                    q.add(new pair(x - 1, y));
                    next++;
                }
                if (isValid(x, y + 1, n, m)
                    && grid[x][y + 1] == 0) {
                    grid[x][y + 1] = 1;
                    q.add(new pair(x, y + 1));
                    next++;
                }
                if (isValid(x, y - 1, n, m)
                    && grid[x][y - 1] == 0) {
                    grid[x][y - 1] = 1;
                    q.add(new pair(x, y - 1));
                    next++;
                }
            }
            if (next == 0)
                break;
            cur = next;
            next = 0;
 
            // Increment time
            t++;
        }
 
        // If no zombie was there in the grid
        // Then it is not possible to convert all
        // the humans to zombie so return -1
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == 0)
                    return -1;
 
        // Return the total time elapsed
        return t;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 3, M = 4;
 
        // Given grid
        int[][] grid = { { 0, 1, 0, 1 },
                         { 0, 0, 0, 0 },
                         { 0, 0, 0, 1 } };
 
        // Function Call
        System.out.print(zombieInfection(grid));
    }
}
 
// This code is contributed by 29AjayKumar

# python program for above approach
from queue import Queue
 
# To check if current coordinate
# lies inside the grid or not
def isValid(i, j, n, m):
 
    if (i < n and i >= 0 and j < m and j >= 0):
        return 1
    else:
        return 0
 
# Function to find out minimum time required
# to infect all humans into zombies
def zombieInfection(grid):
 
    # Queue to store coordinates for BFS
    q = Queue()
 
    # Number of rows
    n = len(grid)
 
    # Number of columns
    m = len(grid[0])
 
    cur = 0
    next = 0
 
    # Initially pushing coordinates of all the
    # zombies into the queue
 
    for i in range(0, n):
        for j in range(0, m):
 
                        # If cell is zombie
            if (grid[i][j] == 1):
                q.put([i, j])
                cur += 1
 
        # To keep track of the time
    t = 0
 
    # While any zombie is left
    while (not q.empty()):
        for i in range(0, cur):
            use = q.get()
            x = use[0]
            y = use[1]
 
            # Checking for all the four directons
            # horizontally and vertically
            if (isValid(x + 1, y, n, m)
                    and grid[x + 1][y] == 0):
                grid[x + 1][y] = 1
                q.put([x + 1, y])
                next += 1
 
            if (isValid(x - 1, y, n, m)
                    and grid[x - 1][y] == 0):
                grid[x - 1][y] = 1
                q.put([x - 1, y])
                next += 1
 
            if (isValid(x, y + 1, n, m)
                    and grid[x][y + 1] == 0):
                grid[x][y + 1] = 1
                q.put([x, y + 1])
                next += 1
 
            if (isValid(x, y - 1, n, m)
                    and grid[x][y - 1] == 0):
                grid[x][y - 1] = 1
                q.put([x, y - 1])
                next += 1
 
        if (next == 0):
            break
 
        cur = next
        next = 0
 
        # Increment time
        t += 1
 
        # If no zombie was there in the grid
        # Then it is not possible to convert all
        # the humans to zombie so return -1
    for i in range(0, n):
        for j in range(0, m):
            if (grid[i][j] == 0):
                return -1
 
        # Return the total time elapsed
    return t
 
# Driver Code
if __name__ == "__main__":
 
    N = 3
    M = 4
 
    # Given grid
    grid = [[0, 1, 0, 1],
            [0, 0, 0, 0],
            [0, 0, 0, 1]]
 
    # Function Call
    print(zombieInfection(grid))
 
    # This code is contributed by rakeshsahni

// C# program for above approach
 
using System;
using System.Collections.Generic;
 
public class GFG {
 
    // To check if current coordinate lies inside the grid
    // or not
    static bool isValid(int i, int j, int n, int m)
    {
        if (i < n && i >= 0 && j < m && j >= 0) {
            return true;
        }
        return false;
    }
 
    class pair {
        public int first, second;
        public pair(int first, int second)
        {
            this.first = first;
            this.second = second;
        }
    }
 
    // Function to find out minimum time required to infect
    // all humans into zombies
    static int zombieInfection(int[, ] grid)
    {
 
        // Queue to store coordinates for BFS
        Queue<pair> q = new Queue<pair>();
 
        // Number of rows
        int n = grid.GetLength(0);
 
        // Number of columns
        int m = grid.GetLength(1);
 
        int cur = 0, next = 0;
 
        // Initially pushing coordinates of all the zombies
        // into the queue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // If cell is zombie
                if (grid[i, j] == 1) {
                    q.Enqueue(new pair(i, j));
                    cur++;
                }
            }
        }
 
        // To keep track of the time
        int t = 0;
 
        // While any zombie is left
        while (q.Count != 0) {
            for (int i = 0; i < cur; i++) {
                pair use = q.Peek();
                q.Dequeue();
                int x = use.first, y = use.second;
 
                // Checking for all the four directons
                // horizontally and vertically
                if (isValid(x + 1, y, n, m)
                    && grid[x + 1, y] == 0) {
                    grid[x + 1, y] = 1;
                    q.Enqueue(new pair(x + 1, y));
                    next++;
                }
                if (isValid(x - 1, y, n, m)
                    && grid[x - 1, y] == 0) {
                    grid[x - 1, y] = 1;
                    q.Enqueue(new pair(x - 1, y));
                    next++;
                }
                if (isValid(x, y + 1, n, m)
                    && grid[x, y + 1] == 0) {
                    grid[x, y + 1] = 1;
                    q.Enqueue(new pair(x, y + 1));
                    next++;
                }
                if (isValid(x, y - 1, n, m)
                    && grid[x, y - 1] == 0) {
                    grid[x, y - 1] = 1;
                    q.Enqueue(new pair(x, y - 1));
                    next++;
                }
            }
            if (next == 0) {
                break;
            }
            cur = next;
            next = 0;
 
            // Increment time
            t++;
        }
 
        // If no zombie was there in the grid
        // Then it is not possible to convert all
        // the humans to zombie so return -1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i, j] == 0) {
                    return -1;
                }
            }
        }
        // Return the total time elapsed
        return t;
    }
 
    static public void Main()
    {
 
        // Code
        // int N = 3, M = 4;
 
        // Given grid
        int[, ] grid = new int[3, 4] { { 0, 1, 0, 1 },
                                       { 0, 0, 0, 0 },
                                       { 0, 0, 0, 1 } };
 
        // Function call
        Console.Write(zombieInfection(grid));
    }
}
 
// This code is contributed by lokesh(lokeshmvs21).

<script>
   // JavaScript code for the above approach
 
   // To check if current coordinate
   // lies inside the grid or not
   function isValid(i, j, n, m) {
     if (i < n && i >= 0 && j < m && j >= 0)
       return 1;
     else
       return 0;
   }
 
   // Function to find out minimum time required
   // to infect all humans into zombies
   function zombieInfection(grid)
   {
    
     // Queue to store coordinates for BFS
     let q = [];
 
     // Number of rows
     let n = grid.length;
 
     // Number of columns
     let m = grid[0].length;
 
     let cur = 0, next = 0;
 
     // Initially pushing coordinates of all the
     // zombies into the queue
     for (let i = 0; i < n; i++) {
       for (let j = 0; j < m; j++) {
 
         // If cell is zombie
         if (grid[i][j] == 1) {
           q.push({ first: i, second: j });
           cur++;
         }
       }
     }
 
     // To keep track of the time
     let t = 0;
 
     // While any zombie is left
     while (q.length != 0) {
       for (let i = 0; i < cur; i++) {
         let use = q[0];
         q.shift();
         let x = use.first, y = use.second;
 
         // Checking for all the four directons
         // horizontally and vertically
         if (isValid(x + 1, y, n, m)
           && grid[x + 1][y] == 0) {
           grid[x + 1][y] = 1;
           q.push({ first: x + 1, second: y });
           next++;
         }
         if (isValid(x - 1, y, n, m)
           && grid[x - 1][y] == 0) {
           grid[x - 1][y] = 1;
           q.push({ first: x - 1, second: y });
           next++;
         }
         if (isValid(x, y + 1, n, m)
           && grid[x][y + 1] == 0) {
           grid[x][y + 1] = 1;
           q.push({ first: x, second: y + 1 });
           next++;
         }
         if (isValid(x, y - 1, n, m)
           && grid[x][y - 1] == 0) {
           grid[x][y - 1] = 1;
           q.push({ first: x, second: y - 1 });
           next++;
         }
       }
       if (next == 0)
         break;
       cur = next;
       next = 0;
 
       // Increment time
       t++;
     }
 
     // If no zombie was there in the grid
     // Then it is not possible to convert all
     // the humans to zombie so return -1
     for (let i = 0; i < n; i++)
       for (let j = 0; j < m; j++)
         if (grid[i][j] == 0)
           return -1;
 
     // Return the total time elapsed
     return t;
   }
 
   // Driver Code
 
   let N = 3, M = 4;
 
   // Given grid
   let grid = [[0, 1, 0, 1],
   [0, 0, 0, 0],
   [0, 0, 0, 1]];
 
   // Function Call
   document.write(zombieInfection(grid));
 
 // This code is contributed by Potta Lokesh
 </script>

3

Complejidad temporal: O(N*M) 
Espacio auxiliar: O(N*M)