P15282 [MCO 2024] Escape

:::epigraph 处理完数字问题后，巨龙 Evirir 已精疲力竭，他决定玩个电子游戏。 ::: 巨龙 Evirir 正在玩一款名为 **《逃脱！》** 的电子游戏！ 游戏在一个 $N$ 行 $M$ 列的网格上进行。行从上到下编号为 $1, 2, \ldots, N$，列从左到右编号为 $1, 2, \ldots, M$。位于第 $i$ 行、第 $j$ 列的单元格记作 $(i, j)$。两个不同的单元格如果共享一条边，则它们是 **相邻** 的（因此每个单元格最多与上下左右 4 个单元格相邻）。形式化地，单元格 $(i, j)$ 与 $(i - 1, j)$、$(i + 1, j)$、$(i, j - 1)$ 和 $(i, j + 1)$ 相邻（如果这些单元格存在）。 网格中的每个单元格都属于以下四种类型之一，每种类型由一个字符表示： - `.` 表示空单元格 - `d` 表示有狗的单元格 - `e` 表示逃生门的单元格 - `#` 表示墙壁单元格 Evirir 想要到达一个逃生门并避开狗。初始时，Evirir 拥有 **2 HP**（生命值），并且位于一个非墙壁单元格上。每一秒，按顺序发生以下事件： - 如果 Evirir 的生命值小于等于 0，则他立即输掉游戏。 - 如果 Evirir 位于逃生门上（且生命值至少为 1），则他立即赢得游戏。 - Evirir 可以选择不移动，或者移动到一个相邻的 **非墙壁** 单元格。 - 随后，每条狗可以选择不移动，或者移动到一个相邻的 **非墙壁** 单元格。多条狗可以移动到同一个单元格。 - 然后，对于每一条与 Evirir 位于同一单元格的狗，该狗会咬 Evirir，使其生命值减少 1。之后，这条狗会从网格中永久消失。 此外，**在游戏开始前，Evirir 必须预先决定他将移动到的整个单元格序列**。也就是说，Evirir 必须在不知道狗的移动策略的情况下，固定他的移动方案。而狗则可以观察 Evirir 的计划并据此移动。 我们称一个单元格是 **必胜** 的，当且仅当它不是墙壁单元格，并且 Evirir 从该单元格出发，按照他的计划移动，**无论狗如何移动**，他都能获胜。注意，Evirir 可以从逃生门或者有狗的单元格开始游戏。 由于巨龙 Evirir 很懒，他请你帮忙计算网格中必胜单元格的数量。

第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 3000$）。 接下来 $N$ 行，描述网格单元格。每行包含 $M$ 个字符。第 $i$ 行第 $j$ 个字符表示单元格 $(i, j)$ 的类型。

输出一个整数，表示 **必胜** 单元格的数量。

#### 注释 假设我们从单元格 $(4, 5)$ 开始，并选择如下所示的路径。 :::align{center} $\tt{...d.}$ $\tt{.e\#e.}$ $\tt{..d\#d}$ $\tt{.XXXX}$ ::: 这里的 $X$ 表示选定的路径。 按照此计划，位于 $(4, 4)$ 的狗保持不动，位于 $(3, 3)$ 的狗则在玩家迈出第一步后立即向下移动。 游戏开始前，玩家拥有 2 HP，并且位于 $(4, 5)$。 :::align{center} $\tt{...d.}$ $\tt{.e\#e.}$ $\tt{..d\#d}$ $\tt{.e.dP}$ ::: $P$ 表示玩家的位置。 现在他向左移动，单元格 $(4, 4)$ 处有一只狗，因此他的生命值降至 1。与此同时，位于 $(3, 3)$ 的狗向下移动，网格变为： :::align{center} $\tt{...d.}$ $\tt{.e\#e.}$ $\tt{...\#d}$ $\tt{.edP.}$ ::: 显然，在玩家下一次向左移动后，他将立即输掉游戏。可以观察到，在考虑了所有可能的路径后，单元格 $(4, 5)$ 并不是一个必胜单元格。 #### 计分 **子任务 1** （$11$ 分）： 网格中至多有一条狗。 **子任务 2** （$13$ 分）： $N = 1$ **子任务 3** （$15$ 分）： $N, M \leq 10$ **子任务 4** （$15$ 分）： $N, M \leq 40$ **子任务 5** （$17$ 分）： 至多有一个逃生门。 **子任务 6** （$19$ 分）： $N, M \leq 2000$ **子任务 7** （$10$ 分）： 无额外限制。 翻译由 DeepSeek 完成