Connection Status:
Competition Arena > InfiniteLab

InfiniteLab

SRM 490 · 2010-03-12 · by Chmel_Tolstiy

SRM 490 · 2010-03-12 · by Chmel_Tolstiy · Search
Class Name: InfiniteLab
Return Type: long
Method Name: getDistance
Arg Types: (vector<string>, long long, int, long long, int)
Problem Statement

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.

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

Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class InfiniteLab with a public method long long getDistance(vector<string> map, long long r1, int c1, long long r2, int c2) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous