5

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

例如：我们应该画一个 3 x 3 板如下（R - 红色，B - 蓝色，G - 绿色）：

B, B, B
B, R, R
B, G, G

绘制操作的最小数量为 4：

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

你会怎么解决？

4

2 回答 2

6

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

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
于 2012-04-28T14:32:02.037 回答
3

对于初学者，您可以尝试进行知情的详尽搜索。

让您的状态图为：G=(V,E)whereV = {all possible boards}和E = {(u,v) | you can move from board u to v within a single operation}。

  • 请注意，您不需要提前生成图表 - 您可以使用successors(board)函数即时生成它，该函数返回给定板的所有后继者。

您还需要h:V->R- 一个评估板1的可接受启发式函数。

现在，您可以运行A*或双向BFS 搜索 [或两者的组合]，您的源将是一个白板，您的目标是请求的板。因为我们使用了可接受的启发式函数 - A* 既是完整的（如果存在，则总是找到解决方案）和最优的（找到最短的解决方案），它会找到最佳解决方案。[同样适用于双向 BFS]。

缺点：

  • 尽管该算法被告知，但它将具有指数行为。但如果是面试问题，我相信没有效率的解决方案总比没有解决方案好。
  • 尽管是完整且最优的——如果没有解决方案——算法可能会陷入无限循环，或者至少是一个很长的循环，直到它意识到它已经排除了所有的可能性。

(1) 可接受启发式的例子是h(board) = #(miscolored_squares)/max{m,n}

于 2012-04-28T14:25:57.640 回答