P8169 [eJOI 2021] Dungeons

You need to play a game on an $N \times M$ map. Each cell on the map is one of the following types: - `.`: empty ground. - `#`: wall. - `o`: coin. - `X`: bomb. - `S`: starting position. Each map contains one or more `S`. When the game starts, your starting point will be chosen as any one of the `S`. Since the map is very dark, you can only see the cells within a $3 \times 3$ square centered at yourself. Also, `X` and `S` will be treated as empty ground (`.`) in your view. Note that you cannot enter a wall (`#`). In each step, you may move one cell in one of four directions: up, down, left, or 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. Before the game starts, you already have the full map (although you do not know which `S` you will start from). If you play with an optimal strategy, find the number of coins you can guarantee to obtain in the worst case.

The first line contains two positive integers $N, M$. The next $N$ lines describe the map. The testdata guarantees that the border of the map (i.e., the first row, last row, first column, and last column) consists entirely of the `#` character.

Output one integer, the number of coins you can guarantee to obtain in the worst case.

#### Explanation for Sample 1 Since there is only one `S`, the starting position is fixed, and you can obtain all coins. #### Explanation for Sample 2 The initial view when starting from the left and right `S` respectively (`@` is the starting point): $$\texttt{\#\#\#\,\,\,\,\,\,\,\,\#\#\#} \\ \texttt{\#@o\,\,\,\,\,\,\,\,o@\#} \\ \texttt{\#\#\#\,\,\,\,\,\,\,\,\#\#\#}$$ Starting from the left `S`, you can obtain $1$ coin; starting from the right one, you can obtain $2$ coins. Therefore, in the worst case you can obtain at most $\min(1,2)=1$ coin. #### Explanation for Sample 3 No matter which `S` you start from, the initial view is: $$\texttt{...} \\ \texttt{.@.} \\ \texttt{...}$$ Since you do not know where exactly you are on the map, the worst case is stepping onto the `X` next to the starting point (which appears as `.` in the view). In this case you cannot obtain any coins, so the answer is $0$. #### Explanation for Sample 4 The initial view when starting from the top-left and bottom-right `S` respectively: $$\texttt{\#..\,\,\,\,\,\,\,\,...} \\ \texttt{.@.\,\,\,\,\,\,\,\,.@.} \\ \texttt{...\,\,\,\,\,\,\,\,..\#}$$ Since the initial views are different, you can determine your exact position on the map by the differences in the `#` cells. Therefore, you can obtain all coins, and the answer is $6$. #### Explanation for Sample 5 First, you may move left for $2$ steps. If you can see `o`, then you can determine that you are on the fourth row, and also pick up the coin on the left. Otherwise, you still cannot determine whether you are on the second row or the sixth row. Then, based on moving left $2$ steps, you can move right $4$ steps (that is, to the cell $2$ steps to the right of the starting point). If the upper-right cell in your view is `.` (which is `X` on the map), then you can determine that you are on the sixth row. In this case you can safely keep moving left to collect the coin(s) in the second column. If the upper-right cell in your view is not `.`, then you only need to keep moving right to collect the coin(s) in the 16th and 17th columns. The answer obtained by this plan is optimal, which is $\min\{1,1,2\}=1$. It is not hard to see that if you move right directly, you might enter `X` immediately. This plan would give an answer of $0$. #### Constraints **This problem uses bundled tests.** Let the number of `S` on the map be $S$. - Subtask 1 (3 pts): $S=1$, there is no `X`, and only the border of the map 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 special constraints. For all testdata, $1 \le N,M \le 400$, $1 \le S \le 60$. #### Notes This problem is translated from [eJOI2021](https://sepi.ro/ejoi/2021) Day 2 B Dungeons. Translated by ChatGPT 5