MAY99_1 - Tom and Jerry

Tom and Jerry is a favourite cartoon of many of us. One day Manku was sitting watching an episode of Tom and Jerry where he found that Tom and Jerry both entered a rectangular maze and Tom was after Jerry, but Jerry being the hero, returned safely.

Manku then start making different scenarios and wondering that if Jerry moves optimally and Tom knows entire path that Jerry is expected to take, then will Jerry be able to escape out of the maze or not?

Moreover Manku added 1 rule to this that if Jerry moves from position A to position B, then at any cost he is not allowed to return from position B to position A.

Jerry, if is at the escape positions of the maze, in the beginning, then he can't exit from that same position.

Moreover he can't escape if he is caught by Tom at any position.

Jerry and Tom can move up, down, left, right or wait at their current position.

If it is guaranteed that either Jerry would escape or Tom would catch him.

All characters at row = 0 or row = m-1 or column = 0 or column = n-1, which are '.' or 'J' or 'T' are escape positions.

Input

Each input file consist of only 1 test case.

First line of input contains 2 numbers m and n, both integers are less than or equal to 100, the size of the rectangular maze.

Then m lines follows containing n characters each.
. means an open space so that tom or jerry can move there
# means a closed place
T means starting position of Tom
J means starting position of Jerry

Output

Output single line containing a character W and integer D, where W is 'J' if Jerry can escape or else 'T' and D is the minimum time taken by Jerry to escape (if W is 'J') or maximum time for which Jerry is alive (if W is 'T')

Example

Input 1:
4 4
#..J
#...
#.T.
####

Output 1:
J 1
Input 2:
6 3
###
#J#
#.T
###
###
#.#

Output 2:
T 2
Input 3:
7 7
......#
.......
.......
...J...
...T...
.......
#......

Output 3:
J 3
Input 4:
7 7
#.....#
#......
#......
J......
#..T...
#......
#......

Output 4:
J 4

Explanation

In the first test case Jerry will move 1 step to his left and would escape.

In the second test case Jerry can't escape so he will remain at his position and will be caught after 2 moves.

In the third test case Jerry will move 3 steps to his left and will escape.

In the fourth test case Jerry will move 1 step to his right and then 3 steps up to escape.


Added by:Mayank Tuteja
Date:2013-01-05
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:self problem

hide comments
2013-01-18 18:59:28 Mayank Tuteja
@Jose
T 4
2013-01-18 18:52:57 Jose Sanchez
What should be the output to this case?
5 5
#####
#J..#
..#.#
#T..#
#####



Last edit: 2013-01-18 19:37:06
2013-01-11 20:10:08 :D
Thank you for the clarification.
2013-01-10 09:45:21 (Tjandra Satria Gunawan)(曾毅昆)
@:D: no, jerry can't back to the position that previously visited by. and yes, jerry is planing the entire possible path to escape.. (not based on Tom movements but Tom move is based on jerry move (he try to catch jerry))..
2013-01-10 08:29:12 :D
I'm really confused about the move restrictions here. Can we revisit previous fields or are we just forbidden to make exactly reverted moves? That is, for fields A,B,C, if we made a move A->B then B->A is forbidden, but can we still do C->A or A->B again?

Second, is Jerry planning the entire path at the start or is he adjusting it basing on Tom movements?

Last edit: 2013-01-11 20:10:43
2013-01-10 01:22:46 (Tjandra Satria Gunawan)(曾毅昆)
@Mehmet Inal: Yes, jerry can't move to places that previously occupied by Tom.
2013-01-09 21:20:39 mehmetin
Can Jerry move to places previously occupied by Tom? It is said that Tom knows the entire path that will be taken by Jerry. So the answer to the question should be no?
2013-01-08 16:08:21 venca venta
My solution works fine on my computer, but here I get WA. Is there something about the output format that I should be aware of? E.g. should there be a space between the letter and the integer in the output?

@venca
yes there is a space between integer and character as shown in the example

Last edit: 2013-01-08 19:09:49
2013-01-08 12:24:27 (Tjandra Satria Gunawan)(曾毅昆)
Thanks for changing the cluster to pyramid ;-)
2013-01-08 12:24:27 (Tjandra Satria Gunawan)(曾毅昆)
Thanks, but how about pyramid cluster? If you set the cluster to cube, the user can easily get AC in 0.00s.. 1s with cube cluster is equivalent to 10s in pyramid cluster.. I think it's better to set 1s in pyramid cluster. And after that you may rejudge all submissions..

Last edit: 2013-01-08 09:36:10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.