P15492 [ICPC 2025 APC] Control Towers

你是一名建筑师，负责设计城市的新机场。完成设计后，你才意识到忘了为控制塔预留位置。 新机场的布局可以用一个 $r$ 行 $c$ 列的二维网格表示，行从上到下编号为 $1$ 到 $r$，列从左到右编号为 $1$ 到 $c$。第 $i$ 行第 $j$ 列的单元格记为 $(i, j)$。每个单元格要么是占用的，要么是空的。 你需要放置四个控制塔（编号为 $1$ 到 $4$），每个控制塔放在不同的空单元格中。为了便于不同塔之间的通信，对于所有 $k = 1, 2, 3$，要求塔 $k$ 和塔 $k+1$ 放置在同一行或同一列。 你需要计算满足上述要求的控制塔放置方式的数量。如果存在某个 $k$ 使得控制塔 $k$ 放置在不同的单元格，则两种方式视为不同。

输入的第一行包含两个整数 $r$ 和 $c$（$1\le r,c\le 2000$）。接下来的 $r$ 行，每行包含一个长度为 $c$ 的字符串。第 $i$ 行第 $j$ 个字符如果是 `#`，表示单元格 $(i, j)$ 被占用；否则是 `.`（点号），表示空单元格。

输出满足上述要求的控制塔放置方式的数量。

**样例输入/输出 #1 的解释** 图 A.1 展示了所有 $10$ 种可能的控制塔放置方式，其中编号为 $1$、$2$、$3$ 和 $4$ 的单元格分别代表控制塔 $1$、$2$、$3$ 和 $4$。 :::align{center}  图 A.1：所有 $10$ 种可能的控制塔放置方式。 ::: **样例输入/输出 #2 的解释** 第 $2$ 行的任何控制塔都不可能和第 $3$ 行的任何控制塔在同一列。由于没有足够的空单元格将四个控制塔全部放在同一行，因此不存在满足上述要求的放置方式。 **样例输入/输出 #3 的解释** 所有 $10\times 9\times 8\times 7 = 5040$ 种控制塔位置的方式都满足上述要求。 **样例输入/输出 #4 的解释** 没有空单元格可以放置任何控制塔。 翻译由 DeepSeek 完成