提示: 欢迎访问OurACM平台
Problem 1039 推箱子问题

Accept: 22    Submit: 413
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem 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

Submit  Back  Status  Discuss