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

-2

我有2行和n列。我必須找到從其他1.分離1例如所需的最小行數：N找到最小數量的水平和垂直線與其他1分開1？

設= 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

請給我提供至少時間複雜度的解決方案。

來源

2017-05-31 Alfran

你有試過什麼嗎？這可能不是你的意圖，但這是作爲「請爲我做作業」的問題。 –

我試過了，但是我的邏輯超過了O（n^2），超過了我提到的問題中提到的時間複雜度。好吧，在嘗試之前我不會問問題。如果你能夠理解我的作業，請做！ – Alfran

如果你解釋你的邏輯，它可能會有所幫助，也許可以調整它。我的猜測是動態編程方法可行。這是一個有趣的問題。由於水平線是可選的，你可以做兩次。一旦水平線和一次沒有，然後採取兩個解決方案中更好的。 –

似乎水平線是最佳解決方案的一部分，只要兩行至少有一個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位前一個垂直線。

來源

2017-05-31 20:15:33

感謝您的努力，我現在得到了邏輯！這將使解決更簡單，並節省不必要的遍歷時間！ :) – Alfran

每次取這個布爾值並檢查是個好主意。 – Alfran

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

回答

相關問題