Problem Description

You need to play a game on a map of size $N \times M$. Each cell on the map can be one of the following types:

• . : Empty space.
• # : Wall.
• o : Coin.
• X : Bomb.
• S : Starting position.

Each map contains one or more S. At the start of the game, your starting point will be randomly selected from any of the S positions. Due to the dim lighting, you can only see the positions within a $3 \times 3$ square centered on yourself. Additionally, X and S are treated as empty spaces (.) in your field of view. Note that you cannot enter walls (#).

You can move in four directions: up, down, left, and right. When you enter a cell with o, you gain 1 coin, and the o in that cell disappears. When you enter a cell with X, you lose all your coins and the game ends.

Determine the maximum number of coins you can collect in the worst-case scenario.

Input Format

The first line contains two positive integers $N$ and $M$.

The next $N$ lines describe the map. The data guarantees that the outer perimeter (i.e., the first and last rows, and the first and last columns) are all # characters.

Output Format

A single integer representing the maximum number of coins you can collect in the worst-case scenario.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4

Sample Input #2

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

Sample Output #2

1

Sample Input #3

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

Sample Output #3

0

Sample Input #4

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

Sample Output #4

6

Sample Input #5

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

Sample Output #5

1

Notes

Sample 1 Explanation

Since there is only one S, the starting point is fixed, and you can collect all the coins.

Sample 2 Explanation

Initial views when starting from the left and right S (with @ as the starting point):

###     ###
#@o     o@#
###     ###

Starting from the left S you can collect 1 coin, and from the right S you can collect 2 coins. Thus, in the worst case, you can collect $\min(1,2)=1$ coin.

Sample 3 Explanation

Regardless of which S is the starting point, the initial view is:

...
.@.
...

Since you don't know the exact position on the map, the worst case is stepping into the X (treated as .) next to the starting point. In this scenario, you cannot collect any coins, so the answer is 0.

Sample 4 Explanation

Initial views when starting from the top-left and bottom-right S:

#..     ...
.@.     .@.
...     ..#

Since the initial views are different, you can determine your exact position on the map by the different # positions. Therefore, you can collect all the coins, and the answer is 6.

Sample 5 Explanation

First, move left 2 steps. If you can see an o, you can determine you are on the fourth row and pick up the left coin.

Otherwise, you cannot determine if you are on the second or sixth row. So, move right 4 steps (to 2 steps right of the starting point). If the top-right of your view is ., you can determine you are on the sixth row. Then, you can safely move left to collect the coins in the second column. If the top-right is not ., you can simply move right to collect the coins in the sixteenth and seventeenth columns.

This strategy yields the optimal answer of $\min\{1,1,2\}=1$.

It is easy to see that moving directly right might result in stepping into an X, yielding an answer of 0.

Data Constraints

This problem is group-tested.

Let $S$ be the number of S in the map.

• Subtask 1 (3 pts): $S=1$, no X and only the outer perimeter has #.
• 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): No additional constraints.

For 100% of the data, $1 \le N,M \le 400$, $1 \le S \le 60$.

Notes

This problem is translated from eJOI2021 Day 2 B Dungeons.

见题面 Input 部分

见题面 Output 部分