There are many big treasures hidden in the caves! However, it is guarded by a vampire. You want to collect as many of these treasures as possible, while avoiding being catched by the vampire. Luckily, the vampire is quite stupid.
The rules are as follows:
.
), and some
contain walls (#
), treasure (T
), you (S
), or the vampire (V
).
Input The first line of input contains two numbers X and Y, which are the dimensions of the board (1 ≤ X ≤ 20, 1 ≤ Y ≤ 15).
The following Y lines contains X characters each. This is the cave map, made of .#TSV
characters. There is at most one S
, at most one V
, and at most six T
.
Output
Output two numbers: the amount of treasure that you are able to collect, and the minimum number of turns required. For now, you do not care about how you will escape the cave...
The solution is as follows (Y-you, V-vampire, y,v-previous positions):
After 8 steps:
.................... .y.....Y..V......... ..y.yyy###.vvv...... ...y###y.#.###v###.. ....#....#.....v.... ....#....#......v... .................vT. ##...............Tv. T#..................
After 12 steps:
.................... .y.....vvvv......... ..y.yyV###.vvv...... ...y###y.#.###v###.. ....#..y.#.....v.... ....#...Y#......v... .................vT. ##...............Tv. T#..................
After 23 steps:
.................... .y.....vvvv......... ..y.yyv###.vvv...... ...y###v.#.###v###.. ....#..yv#.....v.... ....#...v#......v... .........v.....vVYy. ##........v...v..yv. T#.........vvvyyy...
Input
20 9 ...................T .S.................. .......###.......... ....###..#.###.###.. ....#T...#.......... ....#....#.......... .................TT. ##...............TV. T...................
Output
6 44
Input
7 1 STTTTTV
Output
2 2
Input
7 3 ....... STTTT#V .......
Output
4 4
Input
8 6 ........ S....T.. #######. .....#V. .....##. ........
Output
0 0
Input
20 9 .................... .S.................. .......###.......... ....###..#.###.###.. ....#....#.......... ....#....#.......... .................TT. ##...............TV. T#..................
Output
3 23