### Problem Statement

There is an infinite labyrinth somewhere on Earth. It has an infinite number of rows, a fixed number W of columns and consists of 1x1 cells. Each cell can be in one of three states: free cell with a teleport, free cell without a teleport and blocked cell. It is known that each row in the labyrinth contains either 0 or 2 cells with teleports.

The rows and columns of the labyrinth are numbered using integers. The rows are infinite in both directions, so for every integer i (including negative integers) there's a row numbered i. The columns are numbered 0 to W-1, inclusive. A cell in row i and column j is denoted as (i,j).

If you are located in a free cell (i,j), you can perform one of the following actions:
• Walk to another free cell (x,y) adjacent by side to (i,j). In other words, (x,y) must be such that |i-x| + |j-y| = 1. It is impossible to walk outside of the labyrinth.
• If cell (i,j) contains a teleport, you can use it to be transferred to another free cell from the same row that contains a teleport (there's always exactly one such cell). Note that when you are located in a cell with a teleport, it isn't necessary to use the teleport.
Each of the described two actions, that is, walking to an adjacent cell and using a teleport, counts as one move.

You are given a String[] map containing H rows, with each element consisting of W characters. The character j in element i of map represents the state of cell (i,j), where '#' means a blocked cell, '.' means a free cell and 'T' means a free cell with a teleport. Both indices i and j are 0-based, so map describes the states of all cells in rows 0 to H-1, inclusive. For all other cells the following rule applies: the state of cell (i,j) is exactly the same as the state of cell (x,j) if |i-x| is divisible by H. In other words, the given pattern of H rows is repeated an infinite number of times.

Return the minimum number of moves needed to get from cell (r1,c1) to cell (r2,c2). If it is impossible, return -1.

### Definition

 Class: InfiniteLab Method: getDistance Parameters: String[], long, int, long, int Returns: long Method signature: long getDistance(String[] map, long r1, int c1, long r2, int c2) (be sure your method is public)

### Notes

-The start and finish cells (r1,c1) and (r2,c2) are guaranteed to be distinct free cells.

### Constraints

-map will contain between 1 and 20 elements, inclusive.
-Each element of map will contain between 1 and 20 characters, inclusive.
-All elements of map will contain the same number of characters.
-Each character in map will be either '#', '.' or 'T'.
-Each element of map will contain either 0 or 2 'T' characters.
-r1 and r2 will each be between -10^15 and 10^15, inclusive.
-c1 and c2 will each be between 0 and W-1, inclusive, where W is the number of characters in each element of map.
-Cells (r1,c1) and (r2,c2) will both be free cells.
-Cells (r1,c1) and (r2,c2) will be distinct.

### Examples

0)

 ```{"#...##", ".##...", "..#.##", "#.#.##"}``` `1` `0` `5` `3`
`Returns: 7`
 The optimal path is drawn below. Here 'S' means the start cell, 'F' means the finish cell and 'P' means an intermediate cell. ```#...## S##... PP#.## #P#.## #PPP## .##F.. ..#.## #.#.## ``` Note that the labyrinth is infinite, so only its part with rows 0 to 7, inclusive, is shown here and in subsequent examples.
1)

 ```{"##.#.", ".#T#T", "...#.", "##.#."}``` `7` `4` `1` `0`
`Returns: 9`
 ```##.#. F#T#T PPP#. ##P#. ##P#. .#T#T ...#P ##.#S ``` Here we need to use a teleport once.
2)

 ```{"..######.#", ".###T###.T", "..T#.##T##", ".######..#"}``` `1` `0` `6` `4`
`Returns: 11`
 ```..######.# S###T###.T PPT#.##T## .######PP# ..######P# .###T###PT ..T#F##T## .######..# ``` Here we need to use a teleport twice.
3)

 ```{"..#..", ".#.#.", "....."}``` `-29` `2` `19` `2`
`Returns: 54`
4)

 ```{".#.#.", "..#..", ".....", ".....", "..#.."}``` `-999` `3` `100` `2`
`Returns: -1`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11231

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14243&pm=11231

Chmel_Tolstiy

#### Testers:

PabloGilberto , ivan_metelsky , pieguy

Search