P8247 Clash Royale

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.

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 one number: the minimum number of arrows shot.

* 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