实际问题的链接:- 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”。
最佳答案
可能有助于构建完整解决方案的一些想法。看例子,
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
关于algorithm - 如何找到不同可能矩阵的数量?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55195880/