#P2595. [ZJOI2009] 多米诺骨牌
[ZJOI2009] 多米诺骨牌
题目描述
有一个 的矩形表格,其中有一些位置有障碍。现在要在这个表格内放一些 或者 的多米诺骨牌,使得任何两个多米诺骨牌没有重叠部分,任何一个骨牌不能放到障碍上。并且满足任何相邻两行之间都有至少一个骨牌横跨,任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法,注意你并不需要放满所有没有障碍的格子。
输入格式
第一行两个整数 。
接下来 行,每行 个字符,表示这个矩形表格。其中字符 x
表示这个位置有障碍,字符 .
表示没有障碍。
输出格式
一行一个整数,表示不同的放置方法数对 取模的值。
3 3
...
...
...
2
提示
样例解释
两种放置方法分别为:
112 411
4.2 4.2
433 332
注意这里的数字只用于区分骨牌,不同的排列并不代表不同的方案。
数据范围
- 对于 的数据,满足 ;
- 对于 的数据,满足 。
- 对于 的数据,满足 。