T-800's Escape

View as PDF

Submit solution

Points: 10
Time limit: 1.4s
Memory limit: 256M

Problem types
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 R, C, and K (1 \le R,C \le 50, 1 \le K \le 100), 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 R lines contain C 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 K-th step, however he cannot take more than K 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

There are no comments at the moment.