Given a 2D matrix, each cell is either an infected building 1 or a not infected 0 . Infected building can turn adjacent (up/down/left/right) building beings into infected every hour. Find out how many hours does it take to infect the entire society.
Example:
Input:
[0, 1, 1, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 1, 0, 0, 0]
Output: 2Explanation:
At the end of the 1st hour, the status of the society:
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[0, 1, 0, 1, 1],
[1, 1, 1, 0, 1]
At the end of the 2nd hour, the status of the society:
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]
Solution:
This is a typical task about graph problems. We should consider the society as a graph, where each building is a cell of the grid which connects by its edges to adjacent buildings.
Steps:
- Loop through entire society and add the already infected building position into Queue.
- We will keep a counter for already infected buildings , will use this counter to compare with the total available buildings in the society.
3. Find adjacent buildings around each dequeued infected building position.
4. Infect the adjacent buildings.
5. Add their position as well into the queue.
6. Increase the infected buildings counter.
7. Increase number of the hours.
8. Repeat from 2 until all buildings in the society infected.
9. At any time infected buildings count is equal total available buildings in the society will return the no of hours counter.
