Woburn Challenge 2017-18 Round 2 - Senior Division

Problem 2: Don't Follow the Lights

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 (2 ≤ R, C ≤ 1500). 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, R ≤ 100 and C ≤ 100.

Input Format

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

Output Format

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 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.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 6.00s
Memory Limit: 256M
Added: Feb 23, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)