プログラミングパズル：ボードをペイントする方法は？

Question

ペイントするボードはN x Mです。一度に行全体または列全体をペイントすることができます。すべてのボード・セルの色のN x Mマトリックスが与えられていると、ボードを塗装する最小の塗装操作数を見つけることができます。

B、B、B
B、R、R
B：

例えば：（ - 赤、B - - G、青、緑R）次のように我々は、3×3のボードを描くべきです、塗装作業のG、G

最小数は4：

レッドブルー
• ペイント行1
• ペイント行0ブルー

グリーン

ペイント列0と

ペイント行2どのようにそれを解決するのでしょうか？

Answer 1

初心者は、となっています（）。

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が必要になります - ボードを評価admissible heuristic function。

A*またはbi-directional BFS検索[またはその両方の組み合わせ]を実行すると、ソースがホワイトボードになり、ターゲットが要求されたボードになります。許容できるヒューリスティック関数を使用するため、A *はcomplete（常に存在する場合は解を見つける）とoptimal（最短解を見つける）の両方であり、最良の解を見つけることができます。 [双方向BFSの場合も同じです。]

欠点：

• アルゴリズムが通知されますが、それは指数関数的な振る舞いを持つことになります。 しかし、面接の質問であれば、私は非効率な 解決策が解決策ではないと信じています。
• 解決策がない場合は完全で最適ですが、アルゴリズムは無限ループに固定されているかもしれません。許容ヒューリスティックため

（1）の例では、これは楽しみの問題のように見えるh(board) = #(miscolored_squares)/max{m,n}

Answer 2

です。私はいくつかの擬似コードでそれを撮影してみましょう。

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