algorithm - 如何找到不同可能矩阵的数量？

Question

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

给定一个包含 N 行(编号 1 到 N)和 M 列(编号 1 到 M)的网格。让我们用 (r,c) 表示行“r”和列“c”中的单元格。如果网格的两个单元格共用一条边，则它们是相邻的。

此网格的某些单元格包含宝藏。您不知 Prop 体哪些单元格包含它们，但是可以使用称为寻宝图的网格分析。对于每个单元格 (i,j)，您将得到一个整数 A(i,j)，其含义如下:

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

A(i,j)=0: 有偶数个宝藏的格子与格子(i,j)相邻。

A(i,j)=1: 与 (i,j) 格相邻的格子中有奇数个宝藏。

(注:-零被认为是偶数)

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

例子:-

以下 (3 X 2) 矩阵:-

1 -1

1 -1

1 0

答案:- 可能矩阵的数量是“4”。

Answer 1

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

1 -1
1 -1
1  0

y -1
1  x
x  0

零表示两个 x 是宝藏的偶数实例，无论哪种方式都用宝藏固定 y 以满足左中相邻的三个单元格1:

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

唯一有影响的另外两个单元格是左上角和左下角的 1。修复一个，意味着另一个:

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