#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<8<<endl<<1<<endl<<3<<endl<<-1<<endl<<18<<endl<<194<<endl<<-1<<endl<<200;
    return 0;
}

今天小明正在玩《我的世界》，这是一款有趣的游戏，您可以在其中构建自己的虚拟世界。

突然，他发现了一个地下迷宫，其中可能含有大量钻石，这是《我的世界》中的珍贵原材料。

迷宫由路径、土壤和砖块三个部分组成。

小明随身携带一把挖土铲，可以用来挖土，但不能用砖头。游戏轮流进行。每回合小明可以移动一个单位的路径，也可以挖一个单位的土壤（这个回合不移动）。他只能在四个方向（上、下、左、右）移动到相邻的地方。

鉴于迷宫的描述，为了尽快获得这些珍贵的钻石，你能不能找出小明获得这些钻石需要花费的最小回合数吗？

输入格式 输入由多个测试用例组成。

每个测试用例的第一行包含两个整数 M 和 N （2 <= M， N <= 300）。

以下每行包含 N 个大写字母，每个字母分别是“X”（小明）、“D”（菱形）、“B”（砖）、“S”（土壤）和“P”（路径）之一。“X”和“D”都只出现一次。 输出格式 对于每个测试用例，请输出小明在 单独的行。如果小明无法到达菱形，则输出“-1”。

输入数据 1 3 4 XSPS PPBP BBDP 0 0 输出数据 1 8