编程难题:如何画板？

Question

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列

你会如何解决它？

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

Answer 2

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

让你的状态图为：G=(V,E)其中V = {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}