Woburn Challenge 2017-18 Round 2 - Senior Division
Led by the creature Gollum, Frodo and Sam have set out to sneak their way into Mordor. Their journey takes them through the Dead Marshes, a mysterious, ancient battleground which has a way of leaving travellers lost until they perish.
The Dead Marshes can be represented as a 2D grid, with
S
: The starting cell, which is otherwise empty (there's exactly one such cell)D
: The destination cell, which is otherwise empty (there's exactly one such cell).
: An empty cell*
: A cell with a torch
The party would like to reach the destination cell from the starting one as quickly as possible. Every minute, they may move from their current cell to an adjacent one (either up, down, left, or right). They may not move outside the grid, and may not move into a cell containing a torch.
However, empty cells may be dangerous as well, so they've agreed to also
pay attention to the warning words uttered by Gollum: "Don't follow the
lights". To be precise, this means that they may not move in a given
direction if there are at least two cells containing torches further
ahead in that direction, in that same row/column. For example, if
Please help Frodo, Sam, and Gollum determine the minimum amount of time
required for them to reach the destination cell while following the
above rules. Output -1
instead if they can't make it at all, and are
doomed to wander the Dead Marshes forever.
Subtasks
In test cases worth
Input Specification
The first line of input consists of two space-separated integers,
Output Specification
Output a single integer, the minimum amount of time required to reach
the destination cell, or -1
if it's impossible to do so.
Sample Input 1
6 5
**...
.*...
.D.*.
..*..
.....
*..S.
Sample Output 1
7
Sample Input 2
2 10
*....*.D.*
.S.*....*.
Sample Output 2
-1
Sample Explanation 2
In the first case, one optimal path is indicated below:
**...
.*...
6D.*.
5.*..
432..
*.1S.
In the second case, they would need to move up into the
However, moving rightwards in the
Comments