terrain made of these characters:
- "S" is where you are standing now (exactly one);
- "D" is where you need to get to (exactly one);
- "." is dry, walkable ground;
- "X" is rock, which you cannot step on;
- "*" is flooded.
Every second two things happen at once: you move to a cell sharing a side with your current one, and the water spreads, so every dry cell ("." or "S") that shares a side with a flooded cell becomes flooded too. Rock and the D cell never flood.
You cannot step onto a flooded cell, including a cell that floods in the very second you step onto it. You cannot stand still either: each second you must take a step.
Return the fewest seconds needed to reach D, or -1 if it cannot be done.terrain=[['S', '.', '*'], ['.', 'X', '.'], ['.', '.', 'D']] → 4
The way to the right runs next to the water: after the first second it covers (0, 1) and (1, 2), cutting that route off. Going down the left side and along the bottom takes 4 seconds, and the water never gets there in time.
terrain=[['S', '.', '.'], ['*', '.', '.'], ['.', '.', 'D']] → -1
After one second the water covers (0, 0), (1, 1) and (2, 0). The only option is right to (0, 1), then on to (0, 2). By then the water has taken (0, 1) and (1, 2), there is nowhere left to go, and D cannot be reached.
terrain=[['D', 'S'], ['X', '*']] → 1
The goal is right next door: one step left, 1 second.
S, D, ., *, XS cell and exactly one D cellterrain=[['S', '.', '*'], ['.', 'X', '.'], ['.', '.', 'D']]
4
Run checks the first 3 tests in your browser. Submit checks all 88 tests on the server, hidden ones included.