New update is available. Click here to update.

Last Updated: 13 Dec, 2020

Hard

```
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.
```

```
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.
```

```
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.
```

```
You do not need to print anything, It has already been taken care of. Just implement the given function.
```

```
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.

- While spreading the adjacent houses, make sure that the number of days i.e.
- 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.

Similar problems

Minimum Swaps To Make Identical Array

Moderate

Posted: 22 Jan, 2022

Find Center of Star Graph

Easy

Posted: 26 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

COUNT ISLANDS

Moderate

Posted: 14 Sep, 2022

Distance to a Cycle in Undirected Graph

Moderate

Posted: 7 Nov, 2022