谜语:如何改变矩阵颜色？

Question

矩阵M*N.矩阵元素是黑色或白色.我们称相同颜色区域的相邻元素.您可以选择任何区域并翻转其颜色(即更改其所有元素的颜色).给定这样的矩阵,找到使整个矩阵为黑色或白色所需的最小翻转次数.

解决方案:它看起来像一个图形问题.矩阵元素是图顶点.如果对应的矩阵元素是"邻居"并且具有相同的颜色,则连接顶点.答案是图中连接组件的数量.

是否有意义？

修复解决方案:感谢@ypercube和@Billiska,解决方案应修复如下:

• 找到连接的组件(如上所述)并考虑这些组件的图形.
• 找到图形中心,翻转它,创建一个新图形,然后重复直到图形只包含一个顶点.

我们仍然必须证明,翻转图形中心会使翻转次数最小化.

Answer 1

你提出了解决方案:

它看起来像一个图形问题.矩阵元素是图顶点.如果对应的矩阵元素是"邻居"并且具有相同的颜色,则连接顶点.答案是图中连接组件的数量.

而改进:

然后,必须找到"黑色"和"白色"连接组件的数量,并选择两者中最小的组件.

这似乎相当不错,但答案并不像最初看起来那么简单.考虑这个矩阵,其中有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个动作.首先翻转(到白色)中央大黑色组件.结果,翻转的一个和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),并且可以通过始终改变中心区域来实现.