Description

The training ground can be seen as an $n \times m$ character matrix, where each cell is S, K, or ..

S is the "Princess" (Shen Jian You Xia), and K is a skeleton. As everyone knows, the Princess’s arrows can pierce through targets. (We treat the arrow’s range as a ray with infinite length.) Since skeletons are very fragile, they die after being hit once. It is known that all skeletons do not move. What is the minimum number of arrows she needs to shoot to kill all skeletons?

Assume all characters stand on points and have zero size.

Input Format

The first line contains two numbers, $n$ and $m$.

Lines $2$ to $n+1$ each contain $m$ characters, representing skeletons K, empty cells ., and the Princess S. There is only one S.

Output Format

Output one number: the minimum number of arrows shot.

3 5
K...K
.K.K.
..S..

2

3 5
KKKKK
KKSKK
KKKKK

12

Hint

• Subtask 1 (15 points): $1 \le n,m \le 10$.
• Subtask 2 (20 points): $1 \le n,m \le 400$.
• Subtask 3 (35 points): $1 \le n,m \le 10^3$.
• Subtask 4 (30 points): $1 \le n \times m \le 10^6$.

Both $n$ and $m$ are positive integers.

Explanation for Sample $1$:

Translated by ChatGPT 5