P8169 [eJOI 2021] Dungeons

你需要在一个 $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$ 格时，你失去所有金币且游戏结束。 在游戏开始前，你已经获得了完整的地图（尽管你不知道你会以哪个 $\texttt S$ 作为起点）。如果你以最优策略进行游戏，求最坏情况下能够保证获得的金币数量。

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

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

#### 样例 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 X$），那么可以判断位于第六行。这时可以安全地一直向左获得第二列的金币。如果视野不是 $\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](https://sepi.ro/ejoi/2021) Day 2 B Dungeons。