Problem 24406 --biology

## 24406: biology

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 23  Solved: 10
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][176kb]

## Description

这处悬崖可以描述为一个n*m的矩阵，矩阵中s代表落脚点,t代表终点，数字带表一只脚落到上面所需时间，X代表此处无法落脚。攀登时，先把左脚或右脚放在任意一处s,然后另一只脚开始攀登，攀登时，当然是左脚一步，右脚一步。

当任意一只脚落在t处，则攀登结束，为了潘老师的人身安全，为了不被生奥的童鞋们狂虐，你必须算出潘老师最短需要多少时间能攀登结束。

输入数据中包含多组数据

## Output

若无法完成攀登，输出-1【潘老师会果断放弃攀登的^.^

## Sample Input

6 6
4 4 X X T T
4 7 8 2 X 7
3 X X X 1 8
1 2 X X X 6
1 1 2 4 4 7
S S 2 3 X X
10 2
T 1
1 X
1 X
1 X
1 1
1 X
1 X
1 1
1 X
S S
10 2
T X
1 X
1 X
1 X
1 1
1 X
1 X
1 1
1 X
S S
10 10
T T T T T T T T T T
X 2 X X X X X 3 4 X
9 8 9 X X X 2 9 X 9
7 7 X 7 3 X X 8 9 X
8 9 9 9 6 3 X 5 X 5
8 9 9 9 6 X X 5 X 5
8 6 5 4 6 8 X 5 X 5
8 9 3 9 6 8 X 5 X 5
8 3 9 9 6 X X X 5 X
S S S S S S S S S S
7 10
2 3 2 3 2 3 2 3 T T
1 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 3 4
3 2 3 2 3 2 3 2 3 5
3 2 3 1 3 2 3 2 3 5
2 2 3 2 4 2 3 2 3 5
S S 2 3 2 1 2 3 2 3


## Sample Output

12
5
-1
22
12


4 4 X X T T

4 7 8 2 X 7

3 X X X 1 8

1 R X X X 6

1 1 2 4 4 7

L S 2 3 X X

4 4 X X T T

L 7 8 2 X 7

3 X X X 1 8

1 R X X X 6

1 1 2 4 4 7

S S 2 3 X X

4 4 X X T T

L 7 8 R X 7

3 X X X 1 8

1 2 X X X 6

1 1 2 4 4 7

S S 2 3 X X

4 L X X T T

4 7 8 R X 7

3 X X X 1 8

1 2 X X X 6

1 1 2 4 4 7

S S 2 3 X X

4 L X X R T

4 7 8 2 X 7

3 X X X 1 8

1 2 X X X 6

1 1 2 4 4 7

S S 2 3 X X

[Submit][Status]