CSL的校园卡
题号:NC17872
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

今天是阳光明媚,晴空万里的一天,CSL早早就高兴地起床走出寝室到校园里转悠。

但是,等到他回来的时候,发现他的校园卡不见了,于是他需要走遍校园寻找它的校园卡。CSL想要尽快地找回他掉的校园卡,于是便求助于OneDay帮他一起找。

OneDay和CSL在同一已知的地点出发,并以相同的速度(1格/秒)搜索校园,试求两人走遍校园的最短时间。

输入描述:

第一行为两个整数n,m(1 ≤ n, m ≤ 4),表示地图的大小。接下来是n行m列的地图:X表示障碍物,S表示起点,O表示空地。障碍物不能直接经过,数据保证所有空地是可达的,起点有且只有一个。

输出描述:

输出一个整数表示两人共同走遍校园所需的最少时间。
示例1

输入

复制
3 4
XSOO
OOXO
OOOO

输出

复制
5

说明

示例2

输入

复制
2 3
XSX
OOO

输出

复制
2
示例3

输入

复制
4 4
SOOO
OOOO
OOOO
OOOO

输出

复制
8