找到最小數量的水平和垂直線與其他1分開1？

Question

我有2行和n列。 我必須找到從其他1.分離1例如所需的最小行數：N

設= 6

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

我需要繪製這些2行之間1條水平線。 索引之後的2條垂直線（從0開始）2和索引4之後直到底部。

所以總線= 1 + 2 = 3

注意，線可以是任何長度的，即它可以是一個列的長度，但行數應該是最小和各1（矩陣數）應與其他1.

又如分離澄清這更多：

設N = 7

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

在這個例子中我需要1點水平線的d 2條垂直線。 索引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 

所以我們有一個水平線上，3位前一個垂直線，和5位前一個垂直線。