在1s和0的二維數組中找到一個1s的矩形

Question

我有一個2d的對象數組，如果該對象具有單擊設置爲true的屬性，那麼它應該被視爲「1」，否則應該被視爲「0」。這些是被選中的塊。我需要檢查所選框是否形成一個矩形。什麼是最好的方式去做這件事？

Answer 1

你可以解決它這樣：

• 搜索爲1
• 步行水平向右的第一個元素，然後放下，然後離開，再向上
• ，如果你回來起源，你有一個長方形
• 然後確保所有其他元素都爲0

該算法是O（n^2）和作品如果y ou只允許一個矩形。如果你有多個矩形就變得複雜..

Answer 2

我會做這樣的事情（僞）：

// your 2d-array/matrix (N is the number of lines, M the number of columns) 
m[N][M] = ... 

// x coord of top left object containing 1 
baseM = -1 
baseFound = false 
// expected width of rectangle 
width = 0 
widthLocked = false 

// this is set to true after we started recognizing a rectangle and encounter 
// a row where the object expected to be 1 in order to extend the rectangle 
// is 0. 
heightExceeded = false 

// loop over matrix 
for i = 1 to N: // lines 
    // at the beginning of a line, if we already found a base, lock the width 
    // (it cannot be larger than the number of 1s in the row of the base) 
    if baseFound: widthLocked = true 

    for j = 1 to M: // columns 
     if m[i][j] == 1: 
      if not baseFound: 
       baseM = j, baseFound = true 
       width = 1 
      else: 
       if j < baseM: 
        // not in rectangle in negative x direction 
        return false 
       if heightExceeded: 
        // not in rectangle in y direction 
        return false 
       if widthLocked: 
        // not in rectangle in positive x direction 
        if j - baseM >= width: return false 
       else: 
        width = j - baseM 
     elseif baseFound: 
      if widthLocked: 
       // check if we left the rectangle and memorize it 
       if j == baseM: heightExceeded = true 
       if not heightExceeded: 
        // check if object in rectangle is 0 
        if j > baseM && j < baseM + width: return false 
if baseFound: 
    return true 
else: 
    // what is the expected result if no rectangle has been found? 
    return ? 

奔跑在爲O（n）。謹防錯誤。

注：大多數編程語言有0基於陣列，所以你可能需要循環i從0到N - 1，同爲j。

Answer 3

高層：最外層1秒的

• 跟蹤。
• 統計所有的1。
• 如果計數等於被最外層1包圍的區域，我們有一個矩形。

僞代碼：

left = width + 1 
right = 0 
top = height + 1 
bottom = 0 
count = 0 

for x = 1 to width 
for y = 1 to height 
    if grid[x][y] == 1 
    left = min(left , x) 
    right = max(right , x) 
    top = min(top , y) 
    bottom = max(bottom, y) 
    count++ 

if count > 0 and count == (right-left+1)*(bottom-top+1) 
    print "We have a rectangle!" 
else 
    print "We don't have a rectangle!"