2014 Mock CCC by Alex and Timothy

Problem J5: Spacetime Surfer

Alice's love for Bob is everlasting. Unfortunately, they are fated to be apart in the current time. Alas, her burning love cannot be stopped by such a small obstacle. To reach Bob, Alice has acquired a time machine with T (1 ≤ T ≤ 10) settings, along with maps of the terrain from each of those time periods. One of those periods is the present day. Alice and Bob live in a rectangular world that's R units tall by C units wide (1 ≤ R, C ≤ 100). In their world, places where they may walk are denoted by '.'s. and obstacles (places where they may not walk) are denoted by 'X's.

From Alice's perspective of time, it takes 1 second to move in any of the four directions adjacent to her (up, down, left, or right). It also takes her 1 second to travel to any one of the T time periods supported by her time machine. Whenever she travels through time, she always lands exactly on the same location. Of course, she cannot travel to another time if her location in that time is occupied by an obstacle. Alice would like to know the shortest time (from her own perspective) that it takes to get from her location in present day to Bob's location in present day.

Input Format

The first line of input contains the integers R, C, and T, the dimensions of the map and the number of time periods accessible by Alice's time machine.
The following contains T maps, each R rows by C columns. The first of these maps describes the present day. In the present day map, 'A' indicates Alice's current position and 'B' indicates Bob's current position. It is guaranteed that Alice cannot reach Bob from traversing only the present day setting.

Output Format

The shortest time that it takes for Alice to reach Bob, in seconds from Alice's perspective. If this is not possible, output -1.

Sample Input 1

3 3 2
AXX
.X.
XXB
XXX
...
XXX

Sample Output 1

6

Explanation

There are two time settings, depicted below:

(Present Day)
  Setting 0:    Setting 1:
     AXX           XXX
     .X.           ...
     XXB           XXX

The best path Alice can take is: down → travel through time → right → right → travel back to the present day → down to reach Bob.

Sample Input 2

2 5 3
BXXA.
XXX.X
.XXXX
..XXX
X...X
X.X.X

Sample Output 2

8

Explanation

The three time settings are:

(Present Day)
  Setting 0:    Setting 1:     Setting 2:
    BXXA.         .XXXX          X...X
    XXX.X         ..XXX          X.X.X

The best path she can take is: travel to setting 2 → left → left → down → travel to setting 1 → left → up → travel to present day, on top of Bob.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 27, 2014
Author: FatalEagle

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)