Store-Keeper

Time limit1sMemory limit128 MB

Summary

On an n by m grid of cases and empty fields, the keeper walks and pushes a parcel; find the minimum number of pushes to reach the target field.

Level: Medium7 of 10
Topics: BFS, Graph, Shortest path, Implementation
Solved: No attempts yet

Problem

The floor of a store is a rectangle divided into $n \times m$ square fields. Two fields are adjacent if they share a common side. A parcel lies on one of the fields. Each of the remaining fields is either empty or occupied by a case that is too heavy for the store-keeper to move. The store-keeper must shift the parcel from its starting field to the target field.

The store-keeper walks on empty fields, moving one step at a time from the field he stands on to an adjacent empty field. When the store-keeper stands on a field adjacent to the parcel, he may push the parcel so that it moves to the field on the opposite side of the parcel, provided that field does not hold a case.

Write a program that:

reads a store map, the starting position of the store-keeper, and the target position of the parcel from standard input,
computes the minimum number of parcel pushes (the number of times the parcel crosses a field border) needed to place the parcel on the target field, or decides that this is impossible,
writes the result to standard output.

Input

The first line contains two positive integers $n$ and $m$ ( $n, m \le 100$ ) separated by a single space, the dimensions of the store. Each of the next $n$ lines contains one string of length $m$ made of the letters S, M, P, K, w. The $i$ -th character of the $j$ -th line denotes the type of the field with coordinates $(i, j)$ :

S: a case,
M: the starting position of the store-keeper,
P: the starting position of the parcel,
K: the target position of the parcel,
w: an empty field.

Each of the letters M, P, and K appears exactly once.

Output

Print to standard output:

the single word NIE (Polish for "no") if the parcel cannot be placed on the target field,
otherwise a single integer equal to the minimum number of parcel pushes (the number of times the parcel crosses a field border) needed to place the parcel on the target field.

Examples4

Example 1

Input

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

Expected output

Example 2
Input
```
1 5
MPKww
```
Expected output
```
1
```
Example 3
Input
```
1 5
KwPwM
```
Expected output
```
2
```
Example 4
Input
```
1 4
SPKM
```
Expected output
```
NIE
```