2934

2934. 插头DP

题目

给你一个 $n \times m$ 的棋盘，有的格子是障碍，问共有多少条回路满足经过每个非障碍格子恰好一次。

如图，$n=m=4$，$(1,1),(1,2)$ 是障碍，共有 $2$ 条满足要求的回路。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，字符串中只包含 * 和 .，其中 * 表示障碍格子， . 表示非障碍格子。

输出格式

输出一个整数，表示满足条件的回路数量。

数据范围

$2 \le n,m \le 12$

输入样例：

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

输出样例：

2

题解