Given a 2D grid, each cell is either a zombie 1 or human 0. Zombies can turn adjacent horizont or vertical (up/down/left/right) human beings into zombies every hour. The task is to find out how many hours it will take to infect all humans.
Examples:
Input: arr[][] = { { 0, 1, 0, 1 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 1 } };
Output: 3
Explanation: In time = 3 hours all the humans will be converted to zombie.Input: arr[][] = {{ 0, 1, 0 },
{ 0, 0, 0 },
{ 0, 0, 0 }};
Output: 3
Approach: This problem can be solved by using Multi-source BFS. Follow the steps below to solve the given problem.
- Because all the zombies are expanding at the same time so multi-source BFS need to be used.
- Initially push all the zombies positions into the queue.
- While queue is not empty try to visit all the four directions for each zombies because effect of each zombie will be in all the four directions.
- After each set of zombies increment the time by 1.
- At Check if any cell is left to be human that means initially no zombie was there in the grid so return -1.
- Otherwise return the total time taken to infect all the humans.
Below is the implementation of the above approach:
C++14
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// To check if current coordinate// lies inside the grid or notbool 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 zombiesint 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 Codeint 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
// Java program for above approachimport 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 |
Python3
# python program for above approachfrom queue import Queue# To check if current coordinate# lies inside the grid or notdef 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 zombiesdef 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 Codeif __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#
// C# program for above approachusing 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). |
Javascript
<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> |
Output
3
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
