多米诺骨牌

多米诺骨牌

测试数据来自 system/1581

描述

有一个n×m 的矩形表格,其中有一些位置有障碍。现在要在这个表格内放一些1×2 或者2×1 的多米诺骨牌,使得任何两个多米诺骨牌没有重叠部分,任何一个骨牌不能放到障碍上。并且满足任何相邻两行之间都有至少一个骨牌横跨,任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法,注意你并不需要放满所有没有障碍的格子。

格式

输入格式

第一行两个整数n;m。接下来n 行,每行m 个字符,表示这个矩形表格。

其中字符“x” 表示这个位置有障碍,字符“.” 表示没有障碍。

输出格式

一行一个整数,表示不同的放置方法数mod 19901013 的值。

样例1

样例输入1

3 3
...
...
...

样例输出1

2

限制

最长时限达7S

提示

两种放置方法分别为
112 411
4.2 4.2
433 332
注意这里的数字只用于区分骨牌,不同的排列并不代表不同的方案。

对于40% 的数据,满足1 ≤ n;m ≤ 8。

对于90% 的数据,满足1 ≤ n;m ≤ 14。

对于100% 的数据,满足1 ≤ n;m ≤ 15。

来源

NOI2009浙江省省选第一试

信息

ID
1663
难度
(无)
分类
动态规划 | 状态压缩DP 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者