3

有一个矩阵 M*N。矩阵元素是黑色或白色。我们称相邻元素的同色区域。您可以选择任何区域并翻转其颜色（即更改其所有元素的颜色）。给定这样一个矩阵，找出使整个矩阵变为黑色或白色所需的最少翻转次数。

解决方案：它看起来像一个图形问题。矩阵元素是图顶点。如果对应的矩阵元素是“邻居”并且具有相同的颜色，则顶点是连接的。答案是图中连通分量的数量。

是否有意义？

固定解决方案：感谢@ypercube 和@Billiska，解决方案应固定如下：

  • 找到连接的组件（如上）并考虑这些组件的图表。
  • 找到图形中心，翻转它，制作一个新图形，然后重复，直到图形只包含一个顶点。

我们仍然需要证明翻转图形中心会使翻转次数最少。

4

3 回答 3

5

您提出了解决方案：

它看起来像一个图形问题。矩阵元素是图顶点。如果对应的矩阵元素是“邻居”并且具有相同的颜色，则顶点是连接的。答案是图中连通分量的数量。

以及改进：

然后必须找到“黑色”和“白色”连通分量的数量，并选择两者中最小的一个。

这似乎很好，但答案并不像起初看起来那么简单。考虑这个矩阵，其中有 13 个黑色连接组件和 4 个白色连接组件。：

B w B w B w B w B
w w w w B w w w w
B w B B B B B w B
w w B B B B B w w
B B B B B B B B B  
w w B B B B B w w
B w B B B B B w B
w w w w B w w w w
B w B w B w B w B

不过，最小的解决方案只有 2 步。首先翻转（到白色）中央大黑色组件。结果，翻转的 1 个和 4 个白色组件现在连接成一个组件。将其翻转为黑色，所有板都是黑色的。

因此，在这种情况下，最小值只有 2 步，而不是 4 步。

因此，在您建立连接（黑色和白色组件）之后，我们就有了这些组件之间的连接图（就像在@Biliska 的回答中一样）。这是上述矩阵的图表：

        B
        |
     B--w--B
        |
    B   |   B
    |   |   |
B---w---B---w---B
    |   |   |
    B   |   B
        |
     B--w--B
        |
        B

我们现在需要找到图形的中心，或者只是一个中心点，例如一个节点 A，其中到其他节点 B 的最大距离 d(A,B) 是最小的（这个最小的最大距离有时被称为“偏心率”） . 从图中可以明显看出，对于上图，中心点正好有一个，“偏心率”为 2。

当偏心率为n时，至少有一个“最大”路径长度2n-1或2n（2n或2n+1节点）。在我们的例子中：

B-w-B-w-B

由于这些图中的任何路径中的节点都是顺序黑白的，因此不难证明所需的最小更改恰好是n（在这种情况下为 2）并且可以通过始终更改中心区域来实现。

于 2012-11-26T17:56:45.920 回答
3

这个问题可以作为最短路径问题来解决。

将您的问题建模为状态图G=(V,E)，其中V = possible states (matrix states)和E = { (u,v) | can move from state u to state v with single "flip" }

现在，一旦你有了图表——你所要做的就是使用一些最短路径算法。

由于该图未加权 - 您可以使用BFS作为您的最短路径算法。如果你能找到一些可接受的启发式函数——你也可以使用A* 算法——使用下降启发式预计会更快。

于 2012-11-26T18:09:20.527 回答
3

首先，您不再尝试将问题建模为单元的连接图，而实际上您应该将问题建模为区域的连接图

例如

b w b w b
w b b w b
w w b b w

转化为面积符号为：

1 2 3 4 5
6 3 3 4 5
6 6 3 3 7

更好地表示为：

1 - 2   4 - 5
|   | /     |
6 - 3 - - - 7

现在接下来要做的是重复执行flip操作以合并区域。我不确定贪婪地翻转连接最多的区域是否正确。

例如，我将首先翻转区域 3，因为它有 4 个连接。然后我得到：

1       5
  \   /
   (3)

然后再次翻转区域 3，因为它有 2 个连接：

   (3)

完毕

因此，您可以看到flip操作具有将所有相邻节点合并到正在翻转的节点的效果。

编辑：事实上，大多数连接的贪婪翻转区域并不是最佳的。以我之前评论过的一维示例为例。

输入：

             middle
                v
b w b w b w b w b w b w b w b w b
<---4 times--->   <---4 times--->

您可以看到，任何区域的连接次数最多为 2。但最有效的算法只会选择翻转中间区域。

于 2012-11-26T18:18:21.083 回答