algorithm - 编程难题 : How to paint a board?

Question

我们应该绘制一个 N x M 板。我们可以一次绘制整行或整列。给定一个包含所有板单元颜色的 N x M 矩阵，找到绘制板的最少绘画操作数。

例如:我们应该如下绘制一个 3 x 3 的板(R - 红色，B - 蓝色，G - 绿色):

乙乙乙
B, R, R
B、G、G

最少的绘画操作数是4:

• 用蓝色绘制第 0 行
• 用红色绘制第 1 行
• 用绿色绘制第 2 行
• 用蓝色绘制第 0 列

你会怎么解决？

Answer 1

这看起来是个有趣的问题。让我用一些伪代码试一试。

Function MinPaints(Matrix) Returns Integer
    If the matrix is empty return 0
    Find all rows and columns which have a single color
    If there are none, return infinity, since there is no solution
    Set the current minimum to infinity
    For each row or column with single color:
        Remove the row/column from the matrix
        Call MinPaints with the new matrix
        If the result is less than the current minimum, set the current minimum to the result
    End loop
    Return the current minimum + 1
End Function

我认为这会解决你的问题，但我没有尝试任何优化或任何东西。这可能不够快，我不知道。我怀疑这个问题能否在次指数时间内解决。

下面是这个算法如何解决这个例子:

BBB
BRR
BGG
|
+---BRR
|   BGG
|   |
|   +---RR
|   |   GG
|   |   |
|   |   +---GG
|   |   |   |
|   |   |   +---[]
|   |   |   |   |
|   |   |   |   Solvable in 0
|   |   |   |
|   |   |   Solvable in 1
|   |   |
|   |   +---RR
|   |   |   |
|   |   |   +---[]
|   |   |   |   |
|   |   |   |   Solvable in 0
|   |   |   |
|   |   |   Solvable in 1
|   |   |
|   |   Solvable in 2
|   |
|   Solvable in 3
|                       BB
+---Another branch with RR ...
|                       GG
Solvable in 4