SPOJ.com - Problem A_W_S

A_W_S_N - Happy Valentine Day (Valentine Maze Game)

no tags

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)

Submit solution!

hide comments

< Previous 1 2 3 Next >

	kshubham02: 2017-03-24 14:22:17 Same as CLEANRBT, no?
	arpit728: 2016-08-16 02:27:42 @tjandra where can I find editorial to this problem.
	hodobox: 2015-12-10 14:44:39 Awesome problem ^.^
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2015-02-13 05:34:07 @Ahmed AKram: Thanks for your appreciation :) of course I have made 2 more version of this problem: Another Valentine Maze Game (1D) is expected to be easier(?) than this problem. Another Valentine Maze Game (2D) is expected to be harder(?) than this problem.
	Ahmed AKram: 2015-01-30 17:52:02 nice problem :) looking forward to this year's problem!
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2014-11-15 08:52:05 @Akhilesh Anandh: thanks for your suggestion, I'll set the reloaded version of this problem with higher constraints next valentine (14 February 2015). --- btw, I'm happy that many solvers "like" this problem, many positive comments and number of facebook like is highest compared to my other problems :-)
	Akhilesh Anandh: 2014-11-15 00:15:42 @Tjandra: Awesome problem! Changing the number of chocolates to about 15 would make it even more interesting.
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-12-21 19:39:22 @Hussain Kara Fallah: do you want more interesting harder problem? ok, next valentine I'll make my next valentine game more harder, just wait ;-)
	Hussain Kara Fallah: 2013-12-18 05:19:59 you have to reduce time limit to make it more interesting
	Mostafa 36a2: 2013-10-17 12:10:51 @tjandra .. Ok . no problem @everybody rewrite your comments :D

Submit solution!

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 ;-)