这是一个关于二维迷宫的题目。我们要从迷宫的起点 'S' 走到终点 'E'，每一步我们只能选择上下左右四个方向中的一个前进一格。 'W' 代表墙壁，是不能进入的位置，除了墙壁以外的地方都可以走。迷宫内的 'D' 代表一道上锁的门，只有在持有钥匙的时候才能进入。而 'K' 则代表了钥匙，只要进入这一格，就会自动地拿到钥匙。最后 '.' 则是代表空无一物的地方，欢迎自在的游荡。本题的迷宫中，起点、终点、门跟钥匙这四个特殊物件，每一个恰好会出现一次。而且，此迷宫的四周 (最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是墙壁。请问，从起点到终点，最少要走几步呢？

Input

输入的第一行有两个正整数H, W，分别代表迷宫的长跟宽。
接下来的H行代表迷宫，每行有一个长度恰为W的字串，此字串只包含`'S'`, `'E'`, `'W'`, `'D '`, `'K'`, `'.'`这几种字元。

Output

请在一行中输出一个整数代表答案，如果无法从起点走到终点，请输出-1。

Sample 1

4 12
WWWWWWWWWWWW
WE.W.S..W.KW
W..D..W....W
WWWWWWWWWWWW

20

Sample 2

6 6
WWWWWW
WEWS.W
W.WK.W
W.WD.W
W.W..W
WWWWWW

-1

Note

4 ≤ H, W≤ 500
'S', 'E', 'K', 'D'各出现恰好一次
迷宫的四周(最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是 'W'

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
//bfs，广度优先，队列+无循环
using namespace std;
const int N = 510;
char mp[N][N];
int stx, sty, edx, edy;//起点和终点
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };//移动的四个方向
struct Node {
    int x, y, step;
    int flag = 0; //标记当前这一步是否找到钥匙;
};
queue<Node> r;
int bfs(int n, int m)
{
    r.push({ stx,sty,0,0 });
    mp[stx][sty] = 'D';
    /*
      总体思路：
        找到k之前，走过的地方变成D
        找到k之后，走过的地方变成W
    */
    int flagk = 0;
    while (r.size())
    {
        auto f = r.front(); r.pop();
        int x = f.x, y = f.y, step = f.step;

        for (int i = 0; i < 4; i++)
        {
            int tx = x + dir[i][0], ty = y + dir[i][1];
            //出界直接跳过
            if (tx < 1 || ty < 1 || ty > m || tx > n)
                continue;
            //接下来处理各种情况
            if (mp[tx][ty] == 'W')continue;
            if (mp[tx][ty] == 'E')return step + 1;
            if (mp[tx][ty] == 'K')
            {
                flagk = 1;
                mp[tx][ty] = 'W';
                r.push({ tx,ty,step + 1,flagk });
            }
            if (mp[tx][ty] == 'D')
            {
                if (!f.flag) continue;
                r.push({ tx,ty,step + 1,flagk });
                mp[tx][ty] = 'W';
            }
            if (mp[tx][ty] == '.')
            {
                if (f.flag) {
                    r.push({ tx,ty,step + 1,1 });
                    mp[tx][ty] = 'W';
                }
                else {
                    r.push({ tx,ty,step + 1,0 });
                    mp[tx][ty] = 'D';
                }
            }
        }
    }
    return -1;
}

int main()
{
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> mp[i] + 1;
    //从输入中读取迷宫的每一行(输入的是不加空格字符串)，并将其存储到 mp[i] 的第 2 个元素和以后得位置，不会只存在mp[i][1],因为定义的mp类型是char
    //从（1,1）开始方便判断是否越界
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == 'S')
                stx = i, sty = j;//找到起点坐标
        }
    }
    cout << bfs(n, m);
    return 0;
}