推箱子问题

Time Limit: 1000 mSec

Memory Limit: 32768 KB

Description

码头仓库是划分为n×m个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中有的格子是空闲的(没有存放任何货物);有的格子上则已经堆放了沉重的货物。堆放的货物太重了,单凭仓库管理员的力量是无法移动的。现在仓库管理员有一项任务,要将一个小箱子推到指定的格子上去。管理员可以在仓库中移动,但不得跨过沉重的不可移动的货物和箱子。当管理员站在与箱子相邻的格子上时,可以做一次推动,把箱子推到另一个相邻的格子,如下图所示:

由于要推动的箱子很重,仓库管理员为了节省体力,想尽量减少推箱子的次数。你能帮帮他么?

编程任务:
对于给定的仓库布局,以及仓库管理员在仓库中的位置和箱子的开始位置和最后位置,计算出仓库管理员将箱子从开始位置移动到目标位置所需的最少移动次数。

Input

输入第一行有两个数n,m(1<=n,m<=100),表示仓库是n×m个格子的矩形阵列。接下来有n行,每行有m个字符,表示一个格子的状态。
S 表示该格子上放了不可移动的沉重货物;
w 表示该格子上没有存放任何货物;
M 表示仓库管理员的初始位置;
P 表示箱子的初始位置;
K 表示箱子的目标位置。

Output

输出仓库管理员将箱子从开始位置移动到目标位置所需的最少移动次数。如果仓库管理员无法将箱子从开始位置移动到目标位置则输出"No solution!"。

Sample Input

10 12
SSSSSSSSSSSS
SwwwwwwwSSSS
SwSSSSwwSSSS
SwSSSSwwSKSS
SwSSSSwwSwSS
SwwwwwPwwwww
SSSSSSSwSwSw
SSSSSSMwSwww
SSSSSSSSSSSS
SSSSSSSSSSSS

Sample Output

7

Hint

Source


提交代码