CF518F Pasha and Pipe

在一次执政党“A”的会议上，部长 Pavel 提议改善下水道系统，并在城市中新建一条管道。 城市地图是一个 $n \times m$ 的矩形网格。每个格子要么为空（则管道可以通过），要么被占据（管道不能通过）。空格子用字符 $.$ 表示，被占据的格子用字符 $# $ 表示。 管道必须满足以下要求： - 管道宽度为 $1$，形状为折线； - 管道只能经过空格子； - 管道必须从场地的边界上开始，但不能从角落格子开始； - 管道必须在场地的边界上结束且也不能在角落格子结束； - 管道最多只能有 $2$ 个 $90^\circ$ 转弯； - 管道与场地边界格子的重合点恰好为两个格子； - 如果管道是一条直线段，则起点和终点必须分别位于不同的边； - 对于管道上的每一个非边界格子，恰好有两个相邻边上的格子也在管道上； - 对于管道上的每一个边界格子，恰好有一个相邻边上的格子也在管道上。 下面是几组允许的管道示例：

....# ....# .*..#

***** ****. .***.

..#.. ..#*. ..#*.

#...# #..*# #..*#

..... ...*. ...*.

下面是几组不允许的管道示例：

.**.# *...# .*.*#

..... ****. .*.*.

..#.. ..#*. .*#*.

#...# #..*# #*.*#

..... ...*. .***.

在这些示例中，管道用字符 $*$ 表示。 你的任务是编写一个程序，计算在城市中恰好铺设一条符合要求的管道的不同方式有多少种。 如果两种管道至少在一个格子上不同，则认为它们是不同的方案。

输入的第一行为两个整数 $n, m$（$2 \leq n, m \leq 2000$），分别表示 Berland 地图的高度与宽度。 接下来的 $n$ 行，每行包含 $m$ 个字符，表示城市的地图。 如果格子上是字符 $.$，表示该格子为空，管道可以通过。 如果格子上是字符 $# $，表示该格子已被占据，管道不可通过。

输出一行，包含一个整数，表示不同管道铺设方案的数量。

在第一个样例中，共有 $3$ 种方案（用 $*$ 标记）：

.*. .*. ...

.*# **# **#

.*. ... .*.

由 ChatGPT 5 翻译