A_W_S_N - Happy Valentine Day (Valentine Maze Game)

Happy Valentine Day!

Valentine Maze

Picture Source: http://www.printactivities.com/Mazes/Shape_Mazes/Heart_Maze.html

In this valentine day, Tjandra Satria Gunawan (TSG) have a mission to date with A** W****** S****** N******(AWSN), Before TSG meet AWSN, TSG want to collect all the chocolate in entire land/maze then share all the chocolate with AWSN later, but AWSN doesn't like to wait, so TSG must collect all chocolate as fast as possible before meet AWSN. Please help TSG to complete this mission. Given a map size m×n (1<m,n≤100), and the map:

'#' denoting wall (TSG can't walk to this area)

'.' denoting road (TSG can walk to this area)

'C' denoting chocolate (also walkable area, appear less than 10 times on the map)

'T' denoting TSG (also walkable area, only appear once on the map)

'W' denoting AWSN (also walkable area, only appear once on the map)

Tjandra can move up, down, left or right, and cost one unit of time every movement.

Input

The first line of input, there's one integer T (T≤30) denoting number of test case, then T case(s) follow,

For each test case:

--> First line contains two integers m and n denoting size of map

--> next m line(s) contains n characters that's the map description.

Output

For each test case, output minimum of time required to complete this mission, if it's impossible to complete this mission, output "Mission Failed!" without quotes.

Example

Input:
8
3 3
T..
...
..W
3 6
######
#T..W#
######
3 6
######
#T#.W#
######
3 6
##C###
#T..W#
######
3 6
C#C###
.T..W#
######
5 10
##########
#T.#.C#..#
#..#..#..#
#..W..#..#
##########
5 10
##########
#T.#.C#.C#
#..#..#..#
#..W..#..#
##########
5 10
##########
#C.#.C#.C#
#..#..#..#
#..T..W..#
##########

Output:
4
3
Mission Failed!
5
9
12
Mission Failed!
23

Time Limit ≈ 5*(My Program (Semi Bruteforce) Speed)

See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2013-02-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:My Love (A_W_S_N) \(^_^)/ I love her since 2008 (when I was studying at EKASMA High School) until present ;-)

hide comments
2013-10-17 06:10:54 (Tjandra Satria Gunawan)(曾毅昆)
Why all comments become same :-/ SPOJ hack?
2013-09-24 23:11:21 007: Name stolen
@Tjandra
i m getting TLE in this ques
submission link :- http://www.spoj.com/files/src/10109875/

can u suggest me how can i optimize the solution..... will be very grateful to u

thank u

Last edit: 2013-09-24 23:36:01
2013-05-07 15:28:47 Vitalis Salis
Finally learned how to solve these kind of problems. :D
2013-03-06 19:32:36 david_8k
I definitely have learned something of this, great problem.
2013-02-16 14:12:35 :D
Nice classic problem :)
2013-02-14 21:11:27 c[R]@zY f[R]0G
nice question

Last edit: 2013-02-14 21:12:15
2013-02-14 17:56:01 Mosa Osama
@Tjandra: Yessss, Thank you ^_^
2013-02-14 17:34:43 (Tjandra Satria Gunawan)(曾毅昆)
@Mosa Osama: Thanks, and Congratulations, you're the first solver ;-)
2013-02-14 16:59:34 Mosa Osama
@Lakshman: I used a graph algorithm to solve part of the problem, and I know nothing about "Matrix manipulation" :-)
2013-02-14 16:46:20 Mosa Osama
Great problem.. I wish you luck on your mission ;-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.