logo AlgoBeat OnlineJudge
登录 注册

#214697. [COCI 2025/2026 #2] 比赛 / Natjecanje

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

本题满分


在一个 的网格上,有 个包裹要配送到 个不同的格子上。包裹起初在中转站处。

有以下四种格子:

  • .:空格子。
  • #:障碍物。
  • S:中转站。
  • X:包裹要被配送到的格子。

已知:同时至多能带两个包裹;每秒可以向四连通(上下左右)的格子移动一格,但是不能移动到障碍物格子上或者越界。

请求出将所有包裹配送并回到中转站的最短时间,或报告无解。

输入格式

第一行,三个正整数 )。

接下来 行,第 行一个长度为 的字符串 ,字符集为 表示第 行第 列的格子的类型。

特别地,保证 出现恰好 次。

输出格式

若无解,输出一行

否则输出一个正整数,表示答案。

样例

样例输入 1

5 5 3
X...X
.....
.....
.....
S...X

样例输出 1

24

样例输入 2

5 5 4
..X..
#X#..
#...X
.SX#.
.....

样例输出 2

16

数据范围与提示

样例解释

样例一解释:先带着一个包裹配送到右下角,回到中转站;然后带着两个包裹依次配送到左上、右上,最后回到起点。

子任务

  • :无额外限制。