题目描述

本题译自 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

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

数据范围与提示

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