5900 - 状压DP:轮廓线DP:闭合回路(模板题)
时间限制 : 1 秒
内存限制 : 128 MB
给出 n\times m 的方格,有些格子不能铺线,其它格子必须铺,形成一个闭合回路。问有多少种铺法?
输入
第一行,两个整数,分别代表 n,m。
从第二行到第 (n+1) 行,每行有一个长度为 m 的只含 *
和 .
的字符串,*
表不能铺线,.
表必须铺。
输出
输出一行一个整数,表示总方案数。
样例
输入
4 4 **.. .... .... ....
输出
2
输入
4 4 .... .... .... ....
输出
6
提示
数据规模与约定
- 对于 100\% 的数据,保证 2\le n,m\le 12。