STORE - Store-keeper

# 题目描述: --- 有一个仓库被分成n*m 个矩形区域，如果两个区域有一条公共边，则被认为这两个区域相邻。包裹都放在一个区域中，剩余的区域或者空闲或者被集装箱占有，这是因为集装箱太重，仓库管理员不能将集装箱搬走。仓库管理员目是是要将包裹从开始的P区域移动到最后的K区域。他可以从空区域走到与之相邻的一个空区域。当仓库管理员走到与包裹相邻的区域时，它可以推动包裹， --- ## 读入 第一行有两个用单个空格分隔的正整数n,m<=100. 接下来是货物存放二维表.共N行，每行为M 个字母组成的单词，字母分别是S, M, P, K, w. 第i单词的第j个位置表示第i行第j列区域的信息，可能是如下内容: S – 集装箱, M –仓库管理员的位置, P –包裹开始的位置, K –包裹最后的位置, w –空区域. M, P 和 K 在文件中只出现一次. ## 输出 --- 如果包裹不能移动到目的位置，则输出"NO"。 如果包裹能移动到目的位置，则写入包裹最小的移动次数。 翻译来源: Bzoj.

The floor of a store is a rectangle divided into _n\*m_ square fields. Two fields are adjacent, if they have a common side. A parcel lays on one of the fields. Each of the remaining fields is either empty, or occupied by a case, which is too heavy to be moved by a store-keeper. The store-keeper has to shift the parcel from the starting field **P** to the final field **K**. He can move on the empty fields, going from the field on which he stands to a chosen adjacent field. When the store-keeper stays on a field adjacent to the one with the parcel he may push the parcel so that if moves to the next field (i.e. the field on the other side of the parcel), assuming condition that there are no cases on this field. ### Task Write a program, which: - reads from the standard input a store scheme, a starting position of the store-keeper and a final position of the parcel, - computes minimal number of the parcel shifts through borders of fields, which are necessary to put the parcel in the final position or decides that it is impossible to put the parcel there, - writes the result into the standard output.

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case two positive integers separated by a single space, _n,m<=100,_ are written. These are dimensions of the store. In each of the following _n_ lines there appears one _m_-letter word made of letters S, M, P, K, w. A letter on _i_-th position in _j_-th word denotes a type of the field with coordinates (_i,j_) and its meaning is following: - S - case, - M - starting position of the store-keeper, - P - starting position of the parcel, - K - final position of the parcel, - w - empty field. Each letter M, P and K appears in the test case exactly once.

Your program should write to the standard output for each test case: - exactly one word NO if the parcel cannot be put on the target field, - exactly one integer, equal to the minimal number of the parcel shifts through borders of the fields, necessary to put a parcel on a final position, if it is possible to put the parcel there.

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

7