All problems

Escape the Flood

Hard · graph traversal

You are given a rectangular map of a flooding building as a grid of characters, grid. Each cell is one of:

There is exactly one "S" and exactly one "E". There can be any number of "W" cells, including none. A cell is flooded once water has reached it, and it stays flooded for ever.

Time passes in whole minutes. Each minute happens in this order:

  1. You move. You step to a neighbouring cell (up, down, left or right) that is not rock, or you stay where you are. You may not end the move on a flooded cell.
  2. If you are on "E", you have escaped. The minute you reach the exit counts, and the water does not get to move in that minute.
  3. The water spreads. Every flooded cell floods each of its neighbours (up, down, left or right) that is not rock. Water spreads onto ".", "S" and "E" cells alike. If the water now covers the cell you are standing on, you are caught.

Return the smallest number of minutes after which you can be on the exit, or -1 if you cannot escape.

For example, take the single row S.E.W. The water starts on the right, so the water reaches the dot next to it after minute 1, the exit after minute 2 and the dot next to S after minute 3. You step onto the first dot in minute 1 (it is still dry afterwards), then onto E in minute 2. The water would have flooded E in that minute, but you got there first, so the answer is 2.

Examples

Example 1

Input: grid = [["S",".","E",".","W"]]

Output: 2

Minute 1: you step onto the first dot, and the water floods the dot next to W. Minute 2: you step onto E before the water moves, so you escape.

Example 2

Input: grid = [["S",".","E","W"]]

Output: -1

The water floods E at the end of minute 1, so by the time you could step on it in minute 2 it is already flooded. Waiting only lets the water reach you.

Example 3

Input: grid = [["S",".",".",".","E"], ["W","#",".","#","."], [".",".",".",".","."]]

Output: 4

The water starts directly below S and runs along the top row right behind you, flooding each cell in the minute you leave it. You step onto E in minute 4, one minute before it would be flooded.

Constraints