如何找到不同的可能矩阵的数目？

Question

链接到实际问题：- https://www.codechef.com/problems/TREASURE

您将得到一个包含N行(编号从1到N)和M列(编号从1到M)的网格。让我们用(r，c)表示行'r‘和列'c’中的单元格。如果网格的两个单元共享一个边，则它们是相邻的。

这个网格中的一些细胞含有珍宝。您不知道哪些单元格包含它们，但是可以对网格进行分析，称为寻宝地图。对于每个单元格(i，j)，给出一个整数A(i，j)，其含义如下：

A(i，j)=−1:无信息

A(i，j)=0:有一个偶数的单元格包含与单元格(i，j)相邻的一个宝藏。

A(i，j)=1:有一个奇数的单元格包含一个与单元(i，j)相邻的宝藏。

(注：-零被视为偶数)

宝藏布局是包含宝藏的所有单元格的集合。查找与所有给定信息一致的可能的宝藏布局数量。

例子：-

以下(3X2)矩阵：

1 -1

1 -1

1%0

答:可能的矩阵数是'4‘。

Answer 1

一些想法，可能有助于建立一个完整的解决方案。看看这个例子，

1 -1
1 -1
1  0

y -1
1  x
x  0

零表示两个xs是财富的偶数实例，无论哪种方法，都可以用一个宝藏来修复y，以满足左中1附近的三个单元格：

T -1  or  T -1
1  -      1  T
-  0      T  0

另外两个有效果的单元格是左上角的1s。修复其中一个意味着另一个：

1  x  or  1  T
T  x      x  x
1  x      1  T

2*2=4

通常，当两个直接对角线单元或两个由第三个单元分隔的内联单元不是-1时，就会产生限制。我们还可以注意到，本质上有两个独立的矩阵。x的价值只意味着o的宝藏安排，反之亦然：

x o x o x
o x o x o
x o x o x