Problem 21925 --Minecraft Maze

21925: Minecraft Maze

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 10  Solved: 4
[Submit][Status][Web Board][Creator:][下载FPS2元][添加到购物车][下载测试数据2元][20kb]

Description

Today XiaoMing is playing Minecraft, an interesting game in which you can build your own virtual world.

Suddenly he found one underground maze which may contain a lot of diamonds, a precious raw material in Minecraft.

The maze consists of three components, path, soil and brick.

XiaoMing has a digging shovel with him, which can be used to dig away the soil, but not brick. The game plays in turn. Each turn XiaoMing can either move one unit of path, or dig one unit of soil(and no move this turn). He can only move to a neighboring place in four directions(up, down, left, right).

Given the decription of the maze, in order to get these precious diamonds as soon as possible, can you find out the minimum turns XiaoMing has to take to get these diamonds?

Input

The input consists of several test cases.

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 'X' (XiaoMing), 'D' (diamonds), 'B' (Brick), 'S' (soil) and 'P' (path). Both 'X' and 'D' appear only once.

Output

For each test case, please output the minimum turns XiaoMing has to take in a separate line. If XiaoMing can't arrive at the diamonds, output "-1" instead.

Sample Input

3 4
XSPS
PPBP
BBDP
0 0

Sample Output

8

HINT

Source

[Submit][Status]