Covid Spread

Posted: 13 Dec, 2020
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.

Try Problem