大家帮我看看 有什么好的算法
小Z是个仓库管理员，他需要在一个N*M(1<=M<=15, 1<=N<=15)的大长方形仓库上放置危险物品，为了在物品泄漏时尽量少地影响到旁边的物品，不能安排危险物品太过于接近，就是说每个物品的旁边的位置（对角线、水平、垂直）都不能放置另一个物品。功能要求：
1、 求出摆放危险品的方法数Q1。（物品之间没有差异，只是考察安排放置的方法由于方法数可能会过大，因此返回方法数要模1000000001）
2、 当我们定制各行必须放置的危险品数量，又有多少种摆放危险品的方法数Q2呢。（返回方法数要模1000000001）
3、 在我们已有危险品位置的情况下，又有多少种摆放危险品的方法数Q3呢。（不考虑条件2的限制，返回方法数要模1000000001）
4、 在同样是上面已有危险品位置的情况下，最多又能摆放多少个危险品呢？Q4（注意，这里考察的是除去已摆放的物品，还能摆放的物品的最大数量，不考虑条件2的限制）
算法程序的输入输出格式要求：
输入：
第一个整数是测试案例数目T，
每组测试数据包括：
第一行是两个整数为N和M，（行和列，1<=M<=15, 1<=N<=15）
第二行是N个整数，表示每行限制的危险品数量，L1 L2 L3 …… LN，
然后是一个表示已摆放危险品的N*M的地图，’*’表示空地，’+’表示已摆放危险品
