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