#P5056. 【模板】插头dp

【模板】插头dp

题目背景

ural 1519

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

题目描述

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

输入格式

第一行,两个整数,分别代表 n,mn,m

从第二行到第 (n+1)(n+1) 行,每行有一个长度为 mm 的只含 *. 的字符串,* 表不能铺线,. 表必须铺。

输出格式

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

4 4
**..
....
....
....
2
4 4
....
....
....
....
6

提示

数据规模与约定

  • 对于 100%100\% 的数据,保证 2n,m122\le n,m\le 12