WC '17 Contest 2 S2 - Don't Follow the Lights

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.75s
Memory limit: 256M

Author:
Problem type
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 R rows and C columns (2R,C1500). The three travellers seek to find their way from a certain starting cell to a destination one. Some of the cells may contain torches, while each other cell appears to be empty, but may contain dangerous boggy water - it's hard to tell which ones are in fact safe to walk on. Each cell is described by one of four characters:

  • 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 C=6 and a certain row has torches in its 3rd and 6th cells, then the party may not move right from the 1st cell to the 2nd cell in that row, but they may move left from the 2nd cell to the 1st cell, or left/right between the 4th and 5th cells.

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 18/22 of the points, R100 and C100.

Input Specification

The first line of input consists of two space-separated integers, R and C.
R lines follow, the ith of which consists of characters representing the ith row of the grid, for i=1R.

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

Copy
6 5
**...
.*...
.D.*.
..*..
.....
*..S.

Sample Output 1

Copy
7

Sample Input 2

Copy
2 10
*....*.D.*
.S.*....*.

Sample Output 2

Copy
-1

Sample Explanation 2

In the first case, one optimal path is indicated below:

Copy
**...
.*...
6D.*.
5.*..
432..
*.1S.

In the second case, they would need to move up into the 1st row to get around the torch in the 4th cell of the 2nd row.
However, moving rightwards in the 1st row towards the torch in the 6th cell is then forbidden, due to the presence of the torch in the 10th cell as well.


Comments

There are no comments at the moment.