【模板】插头dp

题目背景

ural 1519 陈丹琦《基于连通性状态压缩的动态规划问题》中的例题。

题目描述

给出 $n\times m$ 的方格,有些格子不能铺线,其它格子必须铺,形成一个闭合回路。问有多少种铺法?

输入输出格式

输入格式


第一行,两个整数,分别代表 $n,m$。 从第二行到第 $(n+1)$ 行,每行有一个长度为 $m$ 的只含 `*` 和 `.` 的字符串,`*` 表不能铺线,`.` 表必须铺。

输出格式


输出一行一个整数,表示总方案数。

输入输出样例

输入样例 #1

4 4
**..
....
....
....

输出样例 #1

2

输入样例 #2

4 4
....
....
....
....

输出样例 #2

6

说明

#### 数据规模与约定 - 对于 $100\%$ 的数据,保证 $2\le n,m\le 12$。