本题满分 。
在一个 的网格上,有 个包裹要配送到 个不同的格子上。包裹起初在中转站处。
有以下四种格子:
.
#
S
X
已知:同时至多能带两个包裹;每秒可以向四连通(上下左右)的格子移动一格,但是不能移动到障碍物格子上或者越界。
请求出将所有包裹配送并回到中转站的最短时间,或报告无解。
第一行,三个正整数 (,)。
接下来 行,第 行一个长度为 的字符串 ,字符集为 。 表示第 行第 列的格子的类型。
特别地,保证 出现恰好 次。
若无解,输出一行 。
否则输出一个正整数,表示答案。
5 5 3 X...X ..... ..... ..... S...X
24
5 5 4 ..X.. #X#.. #...X .SX#. .....
16
样例一解释:先带着一个包裹配送到右下角,回到中转站;然后带着两个包裹依次配送到左上、右上,最后回到起点。