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-08 12:24:27 Mayank Tuteja
@abdelkarim
whats wrong in example 3 ??
@venca venta
thnxs that was a mistake in my example and 1st test case too
@tjandra
actually 1st test case m and n were wrongly wriiten
and for rest of the test cases m and n are fine.
And as u said time limit is reduced to 1 sec ;)

Last edit: 2013-01-08 07:47:28
2013-01-08 12:24:27 (Tjandra Satria Gunawan)(曾毅昆)
And I think time limit is too relax, It's better to change the time limit to 1 sec and cluster to pyramid... (How about slow languages like JAVA?) I'm sure java solution still have chance to get AC with that limit...
2013-01-08 12:24:27 (Tjandra Satria Gunawan)(曾毅昆)
Finally AC after ignoring m and n, just take the matrix and count matrix size ;-) Bad input data, but good matrix...

@Tjandra
Actually in 1st example it was 4 4
now that problem is fixed in example and test data also
sorry for that

Last edit: 2013-01-08 07:44:30
2013-01-08 12:24:27 (Tjandra Satria Gunawan)(曾毅昆)
Based on my experiment, matrix size is not (m * n) it's EOF before m*n char input.. that's why I'm getting TLE... please fix it!
2013-01-08 12:24:27 (Tjandra Satria Gunawan)(曾毅昆)
NZEC! test data MUST be incorrect! please check it!
2013-01-08 12:24:27 venca venta
and in example 1, one column is missing
2013-01-08 12:24:27 abdelkarim
@problem setter .
please, check example 3.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.