P83059

吃树

难度 8 级 动态规划(提高) 状态压缩
讨论 统计 4通过 16提交 25%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

我们大多数人都知道,在名为DotA(Defense of the Ancients)的游戏中,Pudge在游戏的第一阶段是一个强大的英雄。然而,当游戏结束时,Pudge不再是一个强大的英雄。

所以Pudge的队友给了他一个新的任务——吃树!

这些树是一个大小为N*M个单元的矩形,每个单元要么只有一棵树,要么什么都没有。Pudge需要做的就是吃掉矩形内的所有树木。

Pudge必须遵守以下几条规则:

I.Pudge必须通过选择一个回路来吃掉树木,然后他会吃掉所选回路中的所有树木。

二、不包含树的单元格是不可访问的,例如,Pudge选择的回路中的每个单元格都必须包含一棵树,当选择回路时,回路中单元格中的树将消失。

III、 Pudge可能会选择一个或多个回路来吃树。

现在Pudge有一个问题,有多少种方法可以吃这些树?

输入

输入由几个测试用例组成。输入的第一行是测试用例的数量。测试用例不超过10例。

对于每种情况,第一行包含整数N和M,1<=N,M<=11。接下来的N行中的每一行都包含M个数字(0或1),用空格隔开。数字0表示没有树的单元格,数字1表示只有一棵树的单元格。

输出

对于每个测试用例,输出一个数字表示方案数。保证不超过long long。使用示例中的格式。

样例

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

提示

测试用例的第一个如上图

来源

HDU

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