Last Updated: 13 Dec, 2020
Covid Spread
Hard
Asked in companies
You are given a city which contains 'N' x 'M' houses, where each house can have one of the following three conditions :
1. The value ‘0’ represents an empty house,
2. The value ‘1’ represents a non-infected person,
3. The value ‘2’ represents an infected person.
It takes one day to propagate the infection from an infected house to its adjacent (Front, Back, Left, Right) non-empty and non-infected house. An empty house can only break the line of propagation of infection.
You need to return the minimum number of days Covid will take to infect each and every house in the city. And for the God’s sake if this is impossible, return -1 instead.
Input format :
The first line contains a single integer ‘T’ denoting the number of test cases. Then 'T' test cases follow.
The first line of each test case will contain two integers ‘N’ and ‘M’ denoting the number of rows and columns, respectively.
Next ‘N’ lines contain ‘M’ space-separated integers each denoting the conditions of the house in the city as above explained.
Output format :
For each test case, print the minimum number of days Covid will take to infect each and every person in the city. If this is impossible, print -1 instead.
The output of every test case will be printed in a separate line.
Note :
You do not need to print anything, It has already been taken care of. Just implement the given function.
Constraints :
1 <= 'T' <= 50
1 <= 'N', 'M' <= 100
0 <= 'houses[i][j]' <= 2
Where houses[i][j] denotes the condition of (i,j) house in the city.
Time limit: 1 sec
Approaches
The idea here is to go through all the houses in the city and we can do that in multiple days. Every day, Covid spreads to the houses that are adjacent to the infected houses on the last day.
Now thinking of the worst-case scenario where one of the corners of the city of size N x M is an infected house and the rest all the houses in the city are non-empty and non-infected, for example:
2 1 1 1
1 1 1 1
1 1 1 1
Here, it will take M+N-1 i.e. 6 days to spread the pandemic in the whole city.
We need to explore all the possibilities where there is a new house infected which was non-infected on the previous day.
So we will go for each day, and check whether we get a new infected house or not. When we reach such a condition where no new infected house found, we can stop exploring and return to the previous day (because there is no change in the condition of the city from the previous day to the current day) if and only if there is no such house which is still non-infected else, return -1. Apart from that if we have found a newly added infected house which was non-infected on the previous day, all the houses that are adjacent to that infected house also become infected so we will go for the next day.
The idea is to use Breadth-First Search. The condition of a house to become infected is when they are adjacent to the infected house. In the previous approach, the idea was based on BFS but the implementation was quite inefficient. So that time can be reduced by using this efficient approach of BFS.
Steps:
- Create an empty queue, let's say infected, which will store a pair of (i, j), where (i, j) denotes the position of the house in the city. And create two variables, first name as minDay which stores the minimum number of days to get all the infected houses in the city and second name as nonInfHouse which will store the number of the non-infected houses.
- Find all the infected houses and push the indices into the queue. And for every non-infected house, we will increment the nonInfHouse.
- Run a loop While the queue (infected) is not empty.
- While spreading the adjacent houses, make sure that the number of days i.e. minDays are incremented only once. And it is not incremented if there are no adjacent non-infected and non-empty houses.
- We dequeue positions of the house from the front of the queue (infected), for each position which is infected we keep on making the adjacent all the houses that are adjacent to that infected house also become infected if and only if they are non-empty and non-infected.
- Finally, return the minimum number of days i.e. minDay if and only if there is no such house which is still non-infected else, return -1.