时间戳

首页 > 解决方案 > 在 2D 矩阵中查找没有可能形成的爆炸性地雷，其中一些单元格包含与它们相邻的偶数/奇数地雷的信息

algorithm - 在 2D 矩阵中查找没有可能形成的爆炸性地雷，其中一些单元格包含与它们相邻的偶数/奇数地雷的信息

问题描述

我正在尝试制作涉及 2D 网格的游戏，其中给出一些提示，玩家可以避免包含爆炸性地雷的单元格。我遇到了一个特定的场景，在给定某些提示的情况下，我想知道有多少种地雷是可能的。

假设有一个二维矩阵。每个牢房可能是空的，也可能包含爆炸性地雷。每个单元格都有一些信息。如果单元格的值为

下面给出了 2d 矩阵的示例：
NN
NN
所有可能的编队都不是 16。ON ON
OE 所有 可能的编队都不是 4。



这些是我手工计算的值。我坚持制作一个有效的程序来计算网格尺寸的所有可能形式

标签： algorithmmatrixdata-structuresdynamic-programming

解决方案

基本上，您必须求解Z / 2上的方程组。这实际上与玩名为 Lights Out 的游戏非常相似。让我们以这个板子为例。

O N
O N
O E

让我们为不同的棋盘位置创建变量。

x11 x12
x21 x22
x31 x32

我们得到这样的方程。每个都O变成一个方程，如(sum of neighbor variables) = 1 (mod 2)。每个都E变成一个方程，如(sum of neighbor variables) = 0 (mod 2)。

x12 + x21       = 1 (mod 2)
x11 + x22 + x31 = 1 (mod 2)
      x21 + x32 = 1 (mod 2)        x22 + x31 = 0 (mod 2)

使用Z /2 上的高斯消元法将这些方程排成行梯形。Z /2 很有趣，因为加法和减法没有区别。简而言之，我们反复选择一个出现在某个剩余方程中的变量，将该方程添加到包含该变量的所有其他方程中，然后将该方程放在一边。我会示范。

x12 + x21 = 1
x11 + x22 + x31 = 1
x21 + x32 = 1
x22 + x31 = 0
----

为了让事情变得有趣，让我们选择x21in x12 + x21 = 1。

x11 + x22 + x31 = 1
(x21 + x32) + (x12 + x21) = (1 + 1) ==> x12 + x32 = 0
x22 + x31 = 0
----
x12 + x21 = 1

请注意x21 + x21和1 + 1都简化为0，因为我们正在工作mod 2。现在让我们选择x22.x11 + x22 + x31 = 1

x12 + x32 = 0
(x22 + x31) + (x11 + x22 + x31) = (0 + 1) ==> x11 = 1
----
x12 + x21 = 1
x11 + x22 + x31 = 1

我们没有放在一边的方程中的所有变量都是不同的，所以接下来的两个步骤很无聊。

----
x12 + x21 = 1
x11 + x22 + x31 = 1
x12 + x32 = 0
x11 = 1

我们有4独立的方程，所以答案是2^(3*2 - 4) = 4解（一般来说，2^(board squares - equations)）。有点无聊的结果，但它就是这样。

当我们减少方程时，会发生两件有趣的事情。让我们考虑以下板。

E E
E E

我们得到以下等式。

x12 + x21 = 1        x11 + x22 = 1
x11 + x22 = 1        x12 + x21 = 1

现在，让我们减少。

x12 + x21 = 1
x11 + x22 = 1
x11 + x22 = 1
x12 + x21 = 1
----

x11 + x22 = 1
x11 + x22 = 1
(x12 + x21) + (x12 + x21) = (1 + 1) ==> 0 = 0
----
x12 + x21 = 1

(x11 + x22) + (x11 + x22) = (1 + 1) ==> 0 = 0
0 = 0
----
x12 + x21 = 1
x11 + x22 = 1

我们最终得到两个退化方程0 = 0。这意味着我们给出了冗余信息，它们不算作独立方程。这里的答案2^(2*2 - 2) = 4又来了。

可能发生的另一件事是我们得到一个方程0 = 1。在这种情况下，没有与提示一致的解决方案。

推荐阅读