仓库管理员(Store-Keeper)

【题目描述】

码头仓库是一块 $N×M$ 个格子的矩形，有的格子是空闲的——没有任何东西，有的格子上已经堆放了沉重的货物，由于太重而不可能再被移动。

现在，仓库管理员有一项任务，要将一个小箱子推到指定的格子上去。管理员可以在仓库中移动，但不得跨过沉重的不可移动的货物和箱子。当管理员站在与箱子相邻的格子上时，他可以做一次推动，把箱子推到另一个相邻的格子。考虑到箱子很重，仓库管理员为了节省体力，想尽量减少推箱子的次数。你能帮帮他么？

【输入格式】

第一行有两个正整数数 $N，M$ （$1<= N,M <=100$），表示仓库是 $N×M$ 的矩形。以下有 $N$ 行，每行有 $M$ 个字符，表示一个格子的状态：

$S$ 表示该格子上放了不可移动的沉重货物;

$w$ 表示该格子上没有任何东西;

$M$ 表示仓库管理员初始的位置;

$P$ 表示箱子的初始位置;

$K$ 表示箱子的目标位置;

【输出格式】

如果有解，请输出仓库管理员最少要推箱子的次数；

如果无解，请输出 $NIE$；

【样例输入1】

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

【样例输出1】

7

【样例1说明】

【样例输入输出2】

样例2下载 

【数据规模与约定】

对于 $20\%$ 的数据，$N + M \leq 10^5$;

对于 $100\%$ 的数据，$5 \leq N, M \leq 100$;