[eJOI 2021] Dungeons

Luogu

IDLGP8169

Time1000ms

Memory512MB

DifficultyP6

2021eJOI（欧洲）

你需要在一个 $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$ 作为起点）。如果你以最优策略进行游戏，求最坏情况下能够保证获得的金币数量。 ## Input 第一行两个正整数 $N,M$。接下来的 $N$ 行用来描述地图。数据保证地图外围（即第一行、最后一行、第一列、最后一列）都是 `#` 字符。 ## Output 一个整数，表示最坏情况下能够保证获得的金币数量。 [samples] ## Note #### 样例 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。

Samples

Input #1

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

Output #1

Input #2

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

Output #2

Input #3

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

Output #3

Input #4

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

Output #4

Input #5

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

Output #5

API Response (JSON)

{
  "problem": {
    "name": "[eJOI 2021] Dungeons",
    "description": {
      "content": "你需要在一个 $N \\times M$ 的地图进行游戏。地图的每个位置包括下列类型： - $\\texttt .$：空地。 - $\\texttt \\#$：墙壁。 - $\\texttt o$：金币。 - $\\texttt X$：炸弹。 - $\\texttt S$：起始位置。 每张地图包含一个或多个 $\\texttt S$。当游戏开始时，你的起点将会被选定为任意一个 $\\texttt S$。由于地图",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8169"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你需要在一个 $N \\times M$ 的地图进行游戏。地图的每个位置包括下列类型：\n\n- $\\texttt .$：空地。\n- $\\texttt \\#$：墙壁。\n- $\\texttt o$：金币。\n- $\\texttt X$：炸弹。\n- $\\texttt S$：起始位置。\n\n每张地图包含一个或多个 $\\texttt S$。当游戏开始时，你的起点将会被选定为任意一个 $\\texttt S$。由于地图...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments