Нахождение Квадраты в массиве

Question

У меня есть 2 двумерный массив, который полон 1s и 0s, такие как

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

Вы можете видеть, что есть квадрат-го массива. Я пытаюсь сделать функцию, которая сделает прямоугольник или список прямоугольников на основе квадрата. Так пример возвратит прямоугольник как

rect.x = 2 
rect.y = 1 
rect.width = 7 
rect.height = 5 

Это код, у меня есть сейчас, но это просто лань не возвращает ничего

Dim rects As New List(Of Rectangle) 
    For imgWidth As Integer = 0 To bow.GetUpperBound(0) 
     For imgHeight As Integer = 0 To bow.GetUpperBound(1) 
      If bow(imgWidth, imgHeight) = 1 Then 

       If bow(imgWidth + 1, imgHeight) = 1 And 
        bow(imgWidth + 2, imgHeight) = 1 And 
        bow(imgWidth, imgHeight + 1) = 1 And 
        bow(imgWidth, imgHeight + 2) = 1 Then 

        Dim r As New Rectangle 

        With r 
         .X = imgWidth 
         .Y = imgHeight 
        End With 

        For rectWidth As Integer = imgWidth To bow.GetUpperBound(0) 
         If bow(rectWidth, imgHeight) = 0 Then 
          r.Width = bow(rectWidth - 1, imgHeight) 
         End If 
        Next 

        For rectHeight As Integer = imgHeight To bow.GetUpperBound(1) 
         If bow(imgWidth, rectHeight) = 0 Then 
          r.Height = bow(rectHeight - 1, imgHeight) 
         End If 
        Next 

        rects.Add(r) 
       End If 
      End If 
     Next 
    Next 

Кроме того, массив должен быть в состоянии иметь более чем один квадратный.

Answer 1

Это, как я хотел бы сделать это:

def rectangles(grid): 
    rows = len(grid) 
    cols = len(grid[0]) 

    hor_ones = [[0]] * rows 
    for r in range(rows): 
    for c in range(cols): 
     hor_ones[r].append(hor_ones[r][c] + grid[r][c]) 

    ver_ones = [[0]] * cols 
    for c in range(cols): 
    for r in range(rows): 
     ver_ones[c].append(ver_ones[c][r] + grid[r][c]) 

    ret = [] 
    for r1 in range(rows): 
    for c1 in range(cols): 
     for r2 in range(r1+1, rows): 
     for c2 in range(c1+1, cols): 
      if all_ones(hor_ones[r1], c1, c2) and all_ones(hor_ones[r2], c1, c2) and all_ones(ver_ones[c1], r1, r2) and all_ones(ver_ones[c2], r1, r2): 
      ret.append((r1, c2, r2, c2)) 
    return ret 

def all_ones(ones, x, y): 
    return ones[y+1] - ones[x] == y - x + 1 

Обратите внимание, что:

• hor_ones[r][c] это число единиц в строке г в первые гр столбцов.
• ver_ones[c][r] - это число единиц в столбце c в первых r строках.

Таким образом, число единиц в строке r и между колоннами c1 и c2 (включительно) составляет:

hor_ones[r][c2+1] - hor_ones[r][c1]

EDIT

Вот мое решение в Java, может быть, это вам легче понять и реализовать в VB.NET:

public static List<Rectangle> findRectangles(int[][] grid) { 
    int rows = grid.length; 
    int cols = grid[0].length; 

    int[][] horOnes = new int[rows][cols+1]; 
    for (int r = 0; r < rows; r++) 
     for (int c = 0; c < cols; c++) 
      horOnes[r][c+1] = horOnes[r][c] + grid[r][c]; 

    int[][] verOnes = new int[cols][rows+1]; 
    for (int c = 0; c < cols; c++) 
     for (int r = 0; r < rows; r++) 
      verOnes[c][r+1] = verOnes[c][r] + grid[r][c]; 

    List<Rectangle> ret = new ArrayList<Rectangle>(); 
    for (int r1 = 0; r1 < rows; r1++) 
     for (int c1 = 0; c1 < cols; c1++) 
      for (int r2 = r1+1; r2 < rows; r2++) 
       for (int c2 = c1+1; c2 < cols; c2++) 
        if (allOnes(horOnes[r1], c1, c2) && allOnes(horOnes[r2], c1, c2) && allOnes(verOnes[c1], r1, r2) && allOnes(verOnes[c2], r1, r2)) 
         ret.add(new Rectangle(r1, c1, r2, c2)); 
    return ret; 
} 

private static boolean allOnes(int[] ones, int x, int y) { 
    return ones[y+1] - ones[x] == y - x + 1; 
}