To watch the youtube video going over this topic, please click here.
A matrix (2D array) has cells that are filled with one of three possible values:
Given a matrix, to return the number of turns it takes until there are no humans left. (And if any human survives, then return -1.) ("Rotting Oranges" problem on Leetcode.)
Solution (Multiple BFS)
The way we'll solve this problem is by updating the matrix each turn by infecting humans next to any zombies.
However, there are two things we need to watch out for:
With this in mind, we'll use a queue to hold each zombie, and for each zombie in the queue we'll process it by allowing it to infect any humans adjacent too it (meaning pushing that newly created zombie onto the queue to be processed later).
However, the part where our code is going to become easier to read (and differs from the Leetcode solution) is that each Zombie in our queue will store their matrix position (i,j) and the turn it got infected. To do this, we'll have a special data structure (a struct or a class) to store this extra info.
The time complexity is O(N), where N is the number of cells in the matrix, since we'll process each cell at most once.
The space complexity is O(N), since at worst the queue holds all zombies. (Meaning we start out with a matrix full of zombies and they all get pushed into the queue.)
Note: This solution is called "multiple BFS" because we're using a queue to traverse nodes (zombies) like the BFS algorithm, but we've got multiple nodes (zombies) being traversed at the same time.
Hi, I'm srcmake. I play video games and develop software.
Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.