问题 24406 --biology

24406: biology

时间限制: 1 Sec  内存限制: 128 MB
提交: 23  解决: 10
[提交][状态][讨论版][命题人:]

题目描述

作为生物奥赛教练员,px老师经常会亲自采集标本。某天,在采集标本的途中,潘老师遇到一处悬崖()

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

若一只脚在(x1,y1),另一只脚落地的范围要保证 |x1-x2|+|y1-y2|<=3,若左脚固定,迈右脚只能往右边迈。右脚固定迈左脚只能向左边迈,如图:

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

 

输入

 输入数据中包含多组数据

对于每组数据,第一行为两个整数,n,m(0<=n,m<=100)

然后就是一个n*m的矩阵,描述悬崖

输出

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

若可以完成攀登,输出最小时间

样例输入

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

样例输出

12
5
-1
22
12

提示

 


第一组(l代表左脚,r代表右脚)



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

来源

 

[提交][状态]