比赛场次 652
比赛名称 赤石大赛
比赛状态 已结束比赛成绩
开始时间 2024-12-20 14:00:00
结束时间 2024-12-20 18:00:00
开放分组 全部用户
注释介绍 赤石大赛(1绿3紫2黑)快来赤石
题目名称 插头dp模板(曼哈顿回路
输入输出 Manhattan.in/out
时间限制 3000 ms (3 s)
内存限制 1024 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分

插头dp模板(曼哈顿回路

★★★★☆   输入文件:Manhattan.in   输出文件:Manhattan.out   简单对比
时间限制:3 s   内存限制:1024 MiB

【题目背景】

状压大王wzh强烈要求COGS添加插头dp

【题目描述】

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

【输入格式】

一行两个整数n,m

接下来n行m个字符,"*"表示不能铺线,"."表示必须铺线

【输出格式】

一行一个数表示方案数

【样例输入】

4 4

**..

....

....

....

【样例输出】

2

【样例说明】

在此键入。

【数据规模与约定】

100pts:n,m<=12

【来源】

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