题目描述

本题译自 eJOI2021 Problem E. Dungeon

《地城探宝: 纸汤》（neta《地城探宝: 石头汤》）已经成为了最流行的游戏，并且你要试玩一下。这个游戏在一个 $N$ 行 $M$ 列的矩形场地上进行，每个单元格可能是如下类型之一：

• 空单元格 .；
• 墙壁 #；
• 金币 o；
• 可爆炸的地雷 X；
• 起点 S。

保证第一行，第一列，最后一行和最后一列只包含墙壁（注意，玩家不能穿墙移动）。场地中可能有一个或更多起点。当游戏开始时，玩家会处于某一个标记为 S 的起点。因为游戏是在地下城中进行，可见度是有限的，因此玩家看不见整个地图，只能看见以他为中心的 $3\times 3$ 方形区域。同时，对于玩家来说地雷和起点看上去和空单元格一样（它们都是不可见的）。

每次移动，玩家只能移动到东西南北四个方向的相邻格子中。如果玩家进入了一个有金币的格子，那么金币会被收集，之后就会从格子中消失。如果玩家进入了有地雷的格子，那么地下城就会崩塌，玩家会失去所有获得的金币，游戏就结束了。

好消息是经过查网上攻略，你获得了地下城的地图。然而你不知道你的起点会是哪儿——但是保证你会从某个起点出发。如果你以最优策略进行游戏，你可以保证最多会获得多少金币（再次，你不知道你的起点是哪个）？

输入格式

第一行两个正整数 $N$ 和 $M$。

接下来 $N$ 行，每行 $M$ 个字符，表示地下城的地图。

输出格式

输出一个整数，表示在不知道起点位置的情况下，最多可以获得的金币个数。

3 7
#######
#Soooo#
#######

4

地图上只有一个起点，因此我们知道玩家会从哪里开始。这种情况下玩家可以收集所有金币。

3 8
########
#SoXooS#
########

1

地图上有两个起点，玩家可以通过在起点所看到的来推断是从哪个起点出发的（$\texttt @$ 是玩家所处的位置）：

$$\begin{align} \texttt{###} \qquad \texttt{###}\\ \texttt{#@o} \qquad \texttt{o@#}\\ \texttt{###} \qquad \texttt{###} \end{align} $$

如果从左侧位置出发，最多能收集 $1$ 个金币，如果从右侧位置出发，最多能收集 $2$ 个金币。因此最坏情况下我们能收集 $1$ 个金币。

7 18
##################
#................#
#.o...SX.......o.#
#.o...X..X.....o.#
#.o.....XS.....o.#
#................#
##################

0

不管出发位置，在最坏情况下，玩家会踩到地雷后输掉游戏。玩家初始看到的区域是：

$$\begin{align} \texttt{...}\\ \texttt{.@.}\\ \texttt{...} \end{align} $$

7 18
##################
#....#...........#
#.o...SX.......o.#
#.o...X..X.....o.#
#.o.....XS.....o.#
#.........#......#
##################

6

根据墙壁的位置（左上或右下），玩家可以判断出自己的起点位置并安全地获得所有 $6$ 枚金币。玩家初始看到的区域将会是下面两个中的一个：

$$\begin{align} \texttt{#..} \qquad \texttt{...}\\ \texttt{.@.} \qquad \texttt{.@.}\\ \texttt{...} \qquad \texttt{..#} \end{align} $$

7 18
##################
#......X..S....oo#
##################
#..o..S.X......o.#
##########X#######
#o.....S...X.....#
##################

1

玩家向左移动两个格子，如果玩家看到了金币，那么他在第四行，所以玩家会获得这个金币。

否则，玩家仍然不知道自己是在第二行还是第六行，所以玩家向右移动四格，如果玩家看见右上角的格子是空的（地雷格显示为空格），那么他就在第六行，所以他会向左移动获得金币。

如果玩家没有在右上角看到一个空格子，那么玩家会向右移动获得两个金币，因为此时玩家在第二行。因此，收集到的最少金币数为 $1$。

我们可以观察到第一步向右走是危险的，因为玩家可能会在从相邻格子获得信息之前进入中间一行的地雷格。

数据范围与提示

• 令 $S$ 为地图上可能的起点数量
• $N\le 400,M\le 400,S\le 60$

#	分值	限制
$1$	$3$	$S=1$。没有地雷。除了第一行，第一列，最后一行和最后一列外没有墙壁
$2$	$7$	$N=3$
$3$	$12$	$S=1$
$4$	$23$	$S=2$
$5$	$41$	$1\le N,M\le 250,1\le S\le 12$
$6$	$14$	无附加限制