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 ~(2 \le R, C \le 1\,500)~. 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 ~3^{rd}~ and ~6^{th}~ cells, then the party may not move right from the ~1^{st}~ cell to the ~2^{nd}~ cell in that row, but they may move left from the ~2^{nd}~ cell to the ~1^{st}~ cell, or left/right between the ~4^{th}~ and ~5^{th}~ 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 \le 100~ and ~C \le 100~.

Input Specification

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 \dots R~.

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 ~1^{st}~ row to get around the torch in the ~4^{th}~ cell of the ~2^{nd}~ row.
However, moving rightwards in the ~1^{st}~ row towards the torch in the ~6^{th}~ cell is then forbidden, due to the presence of the torch in the ~10^{th}~ cell as well.