P83044

铺地砖

难度 初三 动态规划 状态压缩
讨论 统计 26通过 74提交 35.1%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给定n×m的格子,每个格子被染成黑色或者白色。现在要用1×2的砖块覆盖这些格子,要求块与块之间不互相重叠,且覆盖了所有白色格子,但不覆盖任意黑色格子。求一共有多少种覆盖方法。 例如3×3的格子,正中间一个点为黑色,其余为白色,覆盖方案数为2种。

输入

第一行为两个正整数N和M。第二至N+1行为格子色染色情况,1表示已黑色,0表示白色。N和M 不超过15

输出

一共有多少种覆盖方法。

样例

样例 1
输入
3 3
0 0 0
0 1 0
0 0 0
输出
2

来源

动规专题

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交