11221: 迷宫
[Creator : ]
Description
我们要从迷宫的起点 'S' 走到终点 'E'，每一步我们只能选择上下左右四个方向中的一个前进一格。 'W' 代表墙壁，是不能进入的位置，除了墙壁以外的地方都可以走。迷宫内的 'D' 代表一道上锁的门，只有在持有钥匙的时候才能进入。而 'K' 则代表了钥匙，只要进入这一格，就会自动地拿到钥匙。最后 '.' 则是代表空无一物的地方，欢迎自在的游荡。
本题的迷宫中，起点、终点、门跟钥匙这四个特殊物件，每一个恰好会出现一次。而且，此迷宫的四周 (最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是墙壁。
请问，从起点到终点，最少要走几步呢？
Input
输入的第一行有两个正整数H, W，分别代表迷宫的长跟宽。
接下来的H行代表迷宫，每行有一个长度恰为W的字串，此字串只包含`'S'`, `'E'`, `'W'`, `'D '`, `'K'`, `'.'`这几种字元。
接下来的H行代表迷宫，每行有一个长度恰为W的字串，此字串只包含`'S'`, `'E'`, `'W'`, `'D '`, `'K'`, `'.'`这几种字元。
Output
请在一行中输出一个整数代表答案，如果无法从起点走到终点，请输出-1。
Constraints
4 ≤ H, W≤ 500
'S', 'E', 'K', 'D'各出现恰好一次
迷宫的四周(最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是 'W'
'S', 'E', 'K', 'D'各出现恰好一次
迷宫的四周(最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是 'W'
Sample 1 Input
4 12
WWWWWWWWWWWW
WE.W.S..W.KW
W..D..W....W
WWWWWWWWWWWW
Sample 1 Output
20
Sample 2 Input
6 6
WWWWWW
WEWS.W
W.WK.W
W.WD.W
W.W..W
WWWWWW
Sample 2 Output
-1