说明

:::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
...d.
.e#e.
..d#d
.e.d.

14

提示

注释

假设我们从单元格 $(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 完成