问题 21925. -- Minecraft Maze

21925: Minecraft Maze

时间限制: 2 Sec  内存限制: 128 MB
献花: 10  解决: 4
[献花][花圈]

题目描述

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?

输入

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.

输出

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.

样例输入

3 4
XSPS
PPBP
BBDP
0 0

样例输出

8

提示

来源

[献花][花圈]