P14596 [COCI 2025/2026 #2] 比赛 / Natjecanje

本题满分 $110$。

在一个 $n\times m$ 的网格上，有 $k$ 个包裹要配送到 $k$ 个不同的格子上。包裹起初在中转站处。 有以下四种格子： - `.`：空格子。 - `#`：障碍物。 - `S`：中转站。 - `X`：包裹要被配送到的格子。 已知：同时至多能带两个包裹；每秒可以向四连通（上下左右）的格子移动一格，但是不能移动到障碍物格子上或者越界。 请求出将所有包裹配送并回到中转站的最短时间，或报告无解。

第一行，三个正整数 $n,m,k$（$1\le n,m\le 500$，$1\le k\le 67$）。 接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的字符串 $s_i$，字符集为 $\{\texttt{.},\texttt{\#},\texttt{S},\texttt{X}\}$。$s_{i,j}$ 表示第 $i$ 行第 $j$ 列的格子的类型。 特别地，保证 $\texttt{X}$ 出现恰好 $k$ 次。

若无解，输出一行 $-1$。 否则输出一个正整数，表示答案。

### 样例解释 **样例一解释**：先带着一个包裹配送到右下角，回到中转站；然后带着两个包裹依次配送到左上、右上，最后回到起点。 ### 子任务 - $\text{Subtask 1 (17 pts)}$：$k\le 2$； - $\text{Subtask 2 (26 pts)}$：$k\le 16$； - $\text{Subtask 3 (29 pts)}$：$k\le 22$； - $\text{Subtask 4 (38 pts)}$：无额外限制。