UOFTCE  A Brief Expedition
Alice has convinced Bob to accompany her on a shopping trip! For some reason, he seems reluctant to spend too much time on it, but she has every intention of hitting every single store at $M$ ($1 \leq M \leq 100$) different malls today. Still, she's promised to get it over with as quickly as possible.
A given mall can be modelled as a twodimensional grid of cells, with $R$ ($1 \leq R \leq 100$) rows and $C$ ($1 \leq C \leq 100$) columns. Each cell contains either a wall (represented by a "#"), open space ("."), a store ("S", of which there is at least one), or Bob's car ("C", of which there is exactly one). Alice and Bob can walk from one cell to a horizontally or verticallyadjacent one in 1 minute if neither cell is blocked by a wall.
The two of them will start at Bob's car, and walk to a store (possibly passing through other stores on the way) so that Alice can do what she does best, which only takes her 60 minutes. At that point, due to the large volume of items purchased, they'll need to return to the car to drop them off. This process will repeat until all stores in the mall have been visited, in some order. It's guaranteed that each store is reachable from the car.
To reassure Bob that they won't spend too much time at each mall, Alice will leave a stopwatch running until the final items have been dropped off in the car. However, sneaky as she is, Alice will only start timing when she actually starts shopping at the first store they decide to visit. She'd like to know how much time will be spent at each mall  though she's sure that it won't be much at all.
Input
Line 1: 1 integer, $M$
For each mall:
Line 1: 2 integers, $R$ and $C$
Next $R$ lines: $C$ characters, representing the $i$th row of the mall grid, for $i=1..H$
Output
For each mall:
1 integer, the minimal number of minutes required to visit all stores and return to the car, as per Alice's stopwatch.
Example
Input:
2
4 4
..S#
.##C
....
S.#S
1 5
SSCSS
Output:
202
250
Explanation of Sample:
At the first mall, Alice and Bob can decide to visit the top store, followed by the bottomleft, and finally the bottomright. In this case, they'll spend 60 minutes shopping, 8 minutes returning to the car, 5 minutes walking to the second store, 60 minutes shopping, 5 minutes returning to the car, 2 minutes walking to the third store, 60 minutes shopping, and 2 minutes again returning to the car. This is a total of 202 minutes.
At the second mall, they can decide to visit the stores lefttoright. This shopping trip will take $60+2+1+60+1+1+60+1+2+60+2=250$ minutes.
hide comments
nadstratosfer:
20171015 20:06:58
Complained to wifey about TLE, her response: "shouldn't have dragged the man to the shopping with her" =) Finally passed thanks to a kinda DP idea. Great problem, will probably dwell on it for a while despite AC, algo can be improved a lot. 

lalywr:
20160802 20:31:42
AC in 2 GO !! . @kushalanand my approach has a better running time . You need to improve your approach :P 

sathya_dev:
20150921 16:04:56
Solve KOZE problem before solving this..Would be helpful :) 
Added by:  SourSpinach 
Date:  20140218 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem, used in the 2013 UofT ACM Tryouts 