Untitled

unknown
plain_text
a year ago
4.6 kB
1
Indexable
Never
```Your tank can't move through rivers or walls, but it can destroy brick walls by shooting. A brick wall will be turned into empty spaces when you hit it, however, if your shot hit a steel wall, there will be no damage to the wall. In each of your turns, you can choose to move to a neighboring (4 directions, not 8) empty space, or shoot in one of the four directions without a move. The shot will go ahead in that direction, until it go out of the map or hit a wall. If the shot hits a brick wall, the wall will disappear (i.e., in this turn). Well, given the description of a map, the positions of your tank and the target, how many turns will you take at least to arrive there?

Input
There can be more than one test case in the input. The first line has T, the number of test cases.
Then the totally T test cases are provided in the following lines (T<=10).
The first line of each test case contains two integers M and N (2 <= M, N< = 300). Each of the following M lines contains N uppercase letters, each of which is one of 'Y' (you), 'T' (target), 'S' (steel wall), 'B' (brick wall), 'R' (river) and 'E' (empty space). Both 'Y' and 'T' appear only once.
Output
For each test case, please output the turns you take at least in a separate line. If you can't arrive at the target, output "-1" instead.

Sample
Input
1
3 4
YBEB
EERE
SSTE

Output
Case #1
8

input
10
3 4
YBEB
EERE
SSTE
3 4
YBEB
EERE
SSTS
3 4
YESS
EEEE
ESET
3 4
YESS
EEEE
ESBT
8 8
EESEEEEE
YBSEESEE
EEEESESE
ESEEEEES
ESBESEEE
ESSEEBBE
EEEEBBSE
EEBSEETS
15 15
YEEEEEEEEEEEEEE
EEBBEEBESEEESEE
BEEEEESESEEESBB
EEESEESSEEESEEE
EBBEEESBBBBBSEE
EEEBESEEESEEEEE
EESESEEEEEESEEE
BESEEEBEBEEEBEE
ESEEEBEESEEEBBE
SEEEEESSSEEEBEE
EESSESEEESEEEBS
EEEESSSESEEEBES
EEESEEESSSEEEEE
BEEEESBEEEESEBE
EEEBEEESEEEEEET
30 20
SYESSESEEEEBBSEBSBSS
SEEEEBESSSEEEBBSEEES
SSBBEEEESBESSEEESESE
SESBSEEBBBEBSBESSSBE
EBSSSEBSBBBSEEBSSSES
SESEESBSBEBESBBEEEES
ESSSBBESSEESSSSEESEB
SEESSBESSSSSEEESSEES
SESSSSSSESBSEBSSSSES
ESEESESEEEESBBEBBSSS
BBBEEEEBEEEBESBSBEES
EEEESSSESEESBSSBBEEE
SEEBSEBEBBSSSSSSEBSS
SBBBSEEEBESEBSBEBBES
BBESSSSEBBSEBSEEBBEE
ESBSEEEBBSSESESSEBSE
BBBSESSBBEESESBBSSBS
EEBSESSEEEBSBSSSBBES
SSSESSEEESSSSEEEBESE
EEBSBBSESESEEEESEBEE
BSEBESSESBEESSESSBES
SEBBBESEBSEESESESBSE
SSEESEBSSESBSESSBEEE
EBESESSSSESEEEEBSSSE
EEESBEBBBBBSSSSSSEEB
SBSEESEEESSSEESBESEB
SBBBEEEEBSESESEEEBSS
BBESEBSBSSESSBBBBBES
EESSEEEEEESSESSBSESB
BSESSEEBSESSSTSSBBSE
35 55
SEESEESSEBESBSBBBESEEESBESSBSBESSSSBBESEBEESBBSBBSESEEB
ESETESBSYEESEESEBESEEBEEBSBBSBESSESSEESBSBSSEEEBESEESBS
SSEESEESESEESBSSEEEESEEEEESEBSBESSSBEBSESSBEESESSSSESSE
SBSSESESEBSSBSESBBEBSEESESEEEBSESBBSSBSESSBSSEEESSSSESS
SBSSESEEESSEEEESEESBEBSESESEBSSSESEEESSEEEESBSSESEBSBEE
SEEBEEESSSBSEBEBSBSBSEBSBSEEBBSBBSESSSEEESESEEBSESSEEBE
SEEESESESBBEEBEEBSEESESEEESEESEEBEEEEBSSSSSSESSSEEEBEEE
ESSSSBEESBSESSEBEBESESBESSBEBEBEEBEBESSSBSSESEEEEBEBSEE
SSBEBEBBSSESEBSBESSEBEBSBSBEEESESEEBBSSBSSSBSSSESESEEES
SESBEBBSEBSBSSSBBEESESEESEBEEEEBSSESSBSESBESBSSSEESSEEE
EESESSEESEBSSEESBEEESBEESESSEBESEESESESEEEBSEESEBSSSEBS
ESSBEESBEESBSEESSBEEBBSBSBSBESEESBSBSSEBSSSSSSSESESEEES
SSSESEEESEESEEEEESEEEESBBEEBSSBSESBEESSEESSESSESBSBEBSS
BEBBESSSESEBBBSSESEBBEBSEBSEEBSBSESEEESSSEEBSSSBEESSEES
EESSBESSBBBSSSEEBESSSSSSBSEESESEEEBSESEEEESSBESSEESEBEB
SSBBESBEEBBBSSEESESEESBBBSSEBSSESSSEESBEBEEBSESEEEBEEEE
SSSEBBEEESEESBEBSSEESSBBBSSSESSEEBSEEEESSSESSSSBSSSEESS
ESBBBESSESEBBBSEEESSSSSSBSEEEBSESSBBESSSSESEESESEEESSSS
ESSSSSEESBSBEEESSEEBSEESSSSESSSSEESBSSSSEESBEEEEEESSEBE
EEEESBBSBESESEEESEBSBSEEBSEEEESSESESBESBESSSSBESBSESSSB
BBEBEEBSSSSSESSBESESEEEESBBBBEBBBSESEBSSSEEBBBEEEBEBESB
SBESESSBSBESESBESEEESEESBSBSEEESESSESBSBSESESBSBESSSEEB
SEEESEBBSEESSSBSBSSSSSEEESESBESEEESEBEBSBEESESEESSSEEES
EEEEEEBSBBEBSSEESEBEBSSBBESBBSSEESEEEBEEBSESESSSEESEEES
BBSSSSSESSSESBBESSSESSSSSESBESSSSBSSESSSBBSESEBBSBESSEE
SSEESSSBSESSSEEBSSBSBSSBEBSESSSSESSSESESEEESEESEBSESESS
SEESSEEBSBSEEBSBSSSSSEEEESESSSBEESBSSESSEEBBEBSSESEESSE
EESSEBBSESSBESSESESSSSSSSEESSSESESSESBSBBSSESEBSSSSEESS
EEBSBESSSESSEBEBSEBSBSSEEEEESSEBESSEEBESESESSBEEBSEBBBS
SESEESESESESBSEESSBSSEBSBSEEESEESESSEBBSBSEBSSSSSESBESB
EBBBEEBSEBBESBSSESEEEBSSESBSSEBESBSEEESSEESEESEEEBESBSB
BBESSEESEBSEESBSSBESSBSESEEESEESEEBSSESSSSSSSSSSESEESSE
SEESBSEEESEEESSEBSEBSSEESSEEBEBSBBSBSEESESESEBEEEBSSBBS
SSBSSSSSEESSSESEEEBBSSBSSBESSBESSSSBEBSSBSEEESEEBSESBSS
SBSSESBSEEBSESSSSSSSSBSEBBEEBSEEESBSEBEBBSSSSEEEBEEESSS
Case #1
8
Case #2
-1
Case #3
5
Case #4
5
Case #5
13
Case #6
29
Case #7
-1
Case #8
-1
Case #9
228
Case #10
598```