Solution:Minimum Time Takes to Reach Destination Without Drowning
Let’s solve the Minimum Time Takes to Reach Destination Without Drowning problem using the Matrices pattern.
We'll cover the following
Statement
Given a m x n
grid of the string land
. It consists of the following types of cells:
S
: Source cell where you are standing initially.D
: Destination cell where you have to reach..
: These cells are empty.X
: These cells are stone.*
: These cells are flooded.
Each second, you can move to a neighboring cell directly next to your current one. At the same time, any empty cell next to a flooded cell also becomes flooded. There are two challenges in your path:
You can’t step on stone cells.
You can’t step on flooded cells or cells that will flood right when you try to step on them because you’ll drown.
Return the minimum time it takes you to reach the destination from the source in seconds, or
Note: The destination will never be flooded.
Constraints:
m
,n
land
consists only ofS
,D
,.
,*
andX
.There is only one
S
andD
cells in theland
.
Solution
This solution finds the shortest time for source S
to reach destination D
while avoiding flooded cells, which expand to horizontally and vertically adjacent cells after every second. The flood spreads from cells marked *
, and S
can only move to empty cells (marked .
) or reach the destination. The algorithm operates based on a matrix traversal pattern, navigating through a grid (or matrix) where each cell has different statuses. The solution works by alternating the flood spread and the source movement in turns, where both the flood and the source expand their positions at each step. If S
reaches D
before being flooded, the algorithm returns the time taken. Otherwise, it returns
Here’s the step-by-step implementation of the solution:
Start by storing the starting position
S
and all the initial positions of the flood marked as*
in theland
. Store these positions in two separate queues. Themoves
will track their movement while theflood
will simulate how the flood spreads.Use a breadth-first search (BFS) approach, where both the flood and the player take turns moving. For each second:
First, process all the flood cells. The flood spreads to any adjacent empty cells marked as
.
. For each cell that gets flooded:Mark it
*
and add it to theflood
queue.
After processing the flood, move the
S
to any adjacent empty cell or the destination. If theS
reachesD:
Return the
seconds
it took to get there.
After the flood and the
S
have taken turns, increase theseconds
by 1 and repeat the process. TheS
and flood continue expanding until theS
either reaches theD
or no more valid moves are left.If the
S
successfully reaches theD
, return theseconds
taken. If there are no more valid moves for theS
and it hasn’t reachedD
, returnto indicate that there is no valid path.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.