题目描述

你需要在一个 $N \times M$ 的地图进行游戏。地图的每个位置包括下列类型：

• $\texttt .$：空地。
• $\texttt \#$：墙壁。
• $\texttt o$：金币。
• $\texttt X$：炸弹。
• $\texttt S$：起始位置。

每张地图包含一个或多个 $\texttt S$。当游戏开始时，你的起点将会被选定为任意一个 $\texttt S$。由于地图视野较暗，因此你只能看到以自身为中心的 $3 \times 3$ 正方形内的位置。同时，$\texttt X$ 和 $\texttt S$ 在视野中会被视为是空地（$\texttt .$）。注意，你不可以进入墙壁（$\texttt \#$）。

你每一步可以向上下左右四个方向进行移动。当你进入 $\texttt o$ 格时，你会获得 $1$ 枚金币，同时该格的 $\texttt o$ 消失。当你进入 $\texttt X$ 格时，你失去所有金币且游戏结束。

求最坏情况下能够获得金币数量的最大值。

输入格式

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

接下来的 $N$ 行用来描述地图。数据保证地图外围（即第一行、最后一行、第一列、最后一列）都是 # 字符。

输出格式

一个整数，表示最坏情况下能够获得金币数量的最大值。

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

4

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

1

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

0

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

6

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

1

提示

样例 1 解释

由于 $\texttt S$ 只有一个，因此起点固定，可以获得所有金币。

样例 2 解释

分别以左侧和右侧 $\texttt S$ 为起点时的初始视野（$\texttt @$ 为起点）：

$$\texttt{\#\#\#\,\,\,\,\,\,\,\,\#\#\#} \\ \texttt{\#@o\,\,\,\,\,\,\,\,o@\#} \\ \texttt{\#\#\#\,\,\,\,\,\,\,\,\#\#\#} $$

以左侧的 $\texttt S$ 为起点时可获得 $1$ 枚金币，以右侧的为起点时可获得 $2$ 枚。因此在最坏情况下最多可获得 $\min(1,2)=1$ 枚金币。

样例 3 解释

无论起点是哪一个 $\texttt S$，初始视野均为：

$$\texttt{...} \\ \texttt{.@.} \\ \texttt{...}$$

由于不知道当前位置具体在地图上是哪里，因此最坏情况是踏入起点旁边的 $\texttt X$（视野中为 $\texttt .$）。这种情况下不能获得任何金币，答案为 $0$。

样例 4 解释

分别以左上和右下的 $\texttt S$ 为起点时的初始视野：

$$\texttt{\#..\,\,\,\,\,\,\,\,...} \\ \texttt{.@.\,\,\,\,\,\,\,\,.@.} \\ \texttt{...\,\,\,\,\,\,\,\,..\#} $$

由于初始视野不同，因此可以通过 $\texttt \#$ 位置的不同判断在地图上的具体位置。因此可以获得所有金币，答案为 $6$。

样例 5 解释

不妨先向左走 $2$ 步。如果能够看到 $\texttt o$，那么可以判断出位于第四行，同时捡起左侧的金币。

否则仍无法判断位于第二行还是第六行。因此可以在向左 $2$ 步的基础上往右 $4$ 步（即走到起点右侧 $2$ 步的位置）。如果视野右上是 $\texttt .$（在地图中为 $\texttt \#$），那么可以判断位于第六行。这时可以安全地一直向左获得第二列的金币。如果视野不是 $\texttt .$，那么只需一直向右即可获得第十六列和第十七列的金币。

按这种方案得到的答案是最优的，为 $\min\{1,1,2\}=1$。

不难发现，如果直接向右，那么可能直接进入 $\texttt X$——这种方案得到的答案为 $0$。

数据规模与约定

本题采用捆绑测试。

设地图中 $\texttt S$ 的数量为 $S$。

• Subtask 1（3 pts）：$S=1$，不存在 $\texttt X$ 且只有地图外围有 $\texttt \#$。
• Subtask 2（7 pts）：$N=3$。
• Subtask 3（12 pts）：$S=1$。
• Subtask 4（23 pts）：$S=2$。
• Subtask 5（41 pts）：$1 \le N,M \le 250$，$1 \le S \le 12$。
• Subtask 6（14 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N,M \le 400$，$1 \le S \le 60$。

说明

本题译自 eJOI2021 Day 2 B Dungeons。