他の1と1を分離する水平線と垂直線の最小数を見つけますか？

Question

私は2行とn列を持っています。 Iは、例えば、他の1から1を分離するのに必要なライン数の最小値を見つけなければならない：

0 0 1 0 1 1 
1 0 0 1 0 1 

= Nう私は、これらの2行の間に1本の水平ラインを描画する必要があります。 インデックスの後に垂直線が2つ（0から始まる）、インデックス4の後に垂直線が下になります。

だから総ライン=それは一つの列の長さであってもよいが、行の数が最小であるべきである、すなわち行は任意の長さであり得ることを1 + 2 = 3

注各1（行列の数）このもっと明確にするために他の1

別の例から分離されなければならない：この例では

レッツN = 7

1 0 1 0 0 1 1 
0 1 0 0 1 0 0 

Iは、1水平ラインANが必要d 2の垂直線。 インデックス1の後に垂直線1本、インデックス5の後に垂直線（長さが列と同じ長さ）。

だから、総ライン= 1 + 2 = 3

は私に少なくとも時間複雑とソリューションを提供してください。

Answer 1

両方の行に少なくとも1つの値があるときは、水平線が最適解の一部であるように見えます（最適解には垂直線のみがある場合もありますが、常にこれらのいずれかを切り替えることができます水平の場合は垂直線）。だから私たちはそれを受け入れることができます（他のケースは検出しやすく、解決しやすい）。

次に、いくつの行を配置するかについては多くのオプションがありません。これにより、非常に簡単に解決できます。行を左から右へ同時に移動します。あなたが1に遭遇するたびに、あなたが行を置く必要があるかどうかを確認してください。ここではいくつかの擬似コードは次のとおりです。

topRowHas1 := false 
bottomRowHas1 := false 
lines := 1 //the horizontal line 
for location from 0 to n - 1 (inclusive) 
    if (topRow[location] == 1 && topRowHas1) || (bottomRow[location] == 1 && bottomRowHas1) 
     //we have to add a vertical line 
     lines++ 
     topRowHas1 := false 
     bottomRowHas1 := false 
    end if 
    topRowHas1 |= topRow[location] == 1 
    bottomRowHas1 |= bottomRow[location] == 1 
next 

そして、ここではあなたの例のために実行が

0 0 1 0 1 1 
1 0 0 1 0 1 

location topRowHas1 bottomRowHas1 lines 
------------------------------------------ 
       false  false  1 
    0  false  true   1 
    1  false  true   1 
    2  true  true   1 
    3  false  false  2 //vertical line here 
       false  true   2 
    4  true  true   2 
    5  false  false  3 //vertical line here 
       true  true   3 

ですだから我々は、5位の前に1本の水平ライン、3位の前に1本の垂直ライン、および1つの垂直ラインを持っています。