You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

玩过LOL的同学都知道提莫这英雄就是拿来恶心人的，牛宝宝有一个学弟非常喜欢提莫这英雄，但是牛宝宝觉得提莫太猥琐了，对手拿了太恶心，队友拿了不放心。

所以有一句话叫做，团战可以输，提莫必须死！！！

于是就有了接下来的惨烈的一幕：蓝紫双方的召唤师达成共识：先杀了提莫再决一死战！察觉到危险的提莫躲进了一个N行M列的方格森林，并种下大量的蘑菇做陷阱，每个蘑菇占一个格子。这些蘑菇含有剧毒，所以不能走到种有蘑菇的方格上。给出召唤师当前的位置(a,b)以及提莫的位置(x,y)，请求出一条不经过种有蘑菇的方格的最短路径使得召唤师能通向提莫。注意提莫始终在(x,y)不会移动。

牛宝宝的团队里有一群编程水平极高且智商极高的队员，觉得出这样简单的题是对队员的不信任，于是M在某些方格里放了小龙（S）和大龙(D)增加杀死提莫的难度，每个方格里最多放一条龙，必须要杀死方格里的龙才可以继续前进。

从一个格子走到下一个格子需要花费一秒的时间，杀死一条小龙需要花费一秒的时间，杀死一条大龙需要花费两秒的时间。小龙在被杀死后的第5秒钟原地复活，大龙在被杀死后的第10秒钟原地复活。注意大小龙都不会移动，召唤师移动只能往前后左右四个方向。

输入格式

输入第一行包括2个正整数N,M，接下来N行M列是一张地图，地图中A表示召唤师们的当前位置，B表示提莫的位置，X表示这个格子含有蘑菇，S表示这个格子里有小龙，D表示这个格子里有大龙，O表示一个可走的空格子。

输出格式

输出一个整数表示召唤师们可以找到提莫的最短时间，如果召唤师们无法找到提莫则输出“-1”（不包括引号）。

3 6
AOOXXB
OXOOOO
XXXOOO

7

1 2
AB

1

1 4
AOXB

-1

见附件

见附件

附件

file

提示

对于20%的数据$n,m \le 100$

对于50%的数据$n,m \le 1000$,没有大龙和小龙

对于100%的数据$n,m \le 1000$