### Mock CCC 2010 by A.J. and Brian

## T-800's Escape

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

The input starts with a line containing the integers*R*,

*C*, and

*K*(1 ≤

*R*,

*C*≤ 50; 1 ≤

*K*≤ 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

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.

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 3.00s

**Memory Limit:** 256M

**Added:** Feb 19, 2010

**Author:** amleshjk

**Languages Allowed:**

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

## Comments (Search)

It's quiet in here...