InfiniteLab | Topcoder Archive

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

```
{"#...##",
 ".##...",
 "..#.##",
 "#.#.##"}
```
```
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.
```
{"##.#.",
 ".#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.
```
{"..######.#",
 ".###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.

{"..#..",
 ".#.#.",
 "....."}

-29

Returns: 54

{".#.#.",
 "..#..",
 ".....",
 ".....",
 "..#.."}

-999

Returns: -1

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.