#P5056. 【模板】插头dp
【模板】插头dp
题目背景
ural 1519
陈丹琦《基于连通性状态压缩的动态规划问题》中的例题。
题目描述
给出 的方格,有些格子不能铺线,其它格子必须铺,形成一个闭合回路。问有多少种铺法?
输入格式
第一行,两个整数,分别代表 。
从第二行到第 行,每行有一个长度为 的只含 *
和 .
的字符串,*
表不能铺线,.
表必须铺。
输出格式
输出一行一个整数,表示总方案数。
4 4
**..
....
....
....
2
4 4
....
....
....
....
6
提示
数据规模与约定
- 对于 的数据,保证 。