Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

La Casa De Papel

By KIRIN29 · Limits 1s, 512 MB

In the middle of a well planned heist in the bank of Spain, the chief security Gandia fled the hostage situation and got firearms from the panic room well enough to blow up the entire bank. The robbers are now in a horrible situation. They need to find and lock Gandia at any cost. Four of the robbers: Tokyo, Rio, Moscow & Nairobi scattered around the bank guarding specific locations.

Gandia is a tricky one, and he is moving through the ventilator shaft inside the bank to avoid contact with the robbers. His intention is to take them one by one when they are isolated from each other. Gandia also has little time left, so he wants to kill them all as quickly as possible.

Input

First line of input will contain T ≤ 5 the number of test cases, followed by R ≤ 10 & C ≤ 10 the number of row & column. Then there will be a 2d grid, containing following special characters :

  • '.' : Empty space
  • '#': Blocked space
  • 'G': Gandida's location
  • 'T': Tokyo's location
  • 'R': Rio's location
  • 'N': Nairobi's location
  • 'M': Moscow's location

Gandia can move to adjacent cell (up, down, left, right, top-right, top-left, bottom-right, bottom-left) from his current cell. Empty spaces means these are accessible to all. Blocked spaces are not accessible from inside the bank except the ventilator shaft. Moving from one cell to another takes 1 minute & killing takes 2 minutes time.

Note: G, T, R, N, M will occur only once in the grid.

Output

Print a line for each case like following (where x is the case number, y is the number of minutes to kill all) :

  • Case #x: Time taken y minutes

See the sample for better understanding.

Sample

InputOutput
1
5 5
GTRMN
#####
#####
#####
#####
Case #1: Time taken 12 minutes

First Gandia goes to cell where Tokyo is (takes 1 minute) and kills her (takes another 2 minutes). Then he moves on to kill Rio and so on. Thus total takes 12 minutes.


    Discussion

    Statistics


    67% Solution Ratio

    edge555Earliest, 1M ago

    edge555Fastest, 0.0s

    alamkhanLightest, 0 B

    rithyyShortest, 2049B

    Submit

    Login to submit