Mock CCC 2010 by A.J. and Brian
T-800, our friendly neighbourhood technologically advanced android, is trying to get away from the not-so-friendly T-1000s. He has to manoeuvre through a maze of buildings to reach his escape pod. However, there is a slight problem: T-800 can only move a certain number of steps before running out of power. So, T-800 has to recharge every so often on one of the recharging pads on the way to his escape pod. Given a map of the maze, help T-800 reach his escape pod as fast as possible.
Input Specification
The input starts with a line containing the integers , , and
, representing the number of rows
and columns in the maze and the maximum number of steps T-800 can take
before having to recharge, respectively. The next lines contain
characters each describing the actual maze: .
represents a free
space, #
represents a building, T
represents T-800's initial
position, R
represents a recharging pad, and E
represents the
escape pod. Note that T-800 can step onto a recharging pad to completely
recharge himself even on his -th step, however he cannot
take more than steps at a time without recharging first. Also note
that T-800 can only take a step to any square adjacent to his current
position (no diagonal moves permitted).
Output Specification
Output the minimum number of steps T-800 has to take in order to reach
his escape pod. If it is impossible for him to reach his escape pod,
output T-800 Terminated.
Sample Input 1
5 5 3
#E...
#....
#.R..
#..T.
#####
Sample Output 1
5
Sample Input 2
5 5 2
#####
#E..#
#..R#
#..T#
#####
Sample Output 2
T-800 Terminated.
Comments