Carrés Trouver dans un tableau

Question

I ont un tableau à 2 dimensions qui est plein de 1 et de 0, comme

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 

Vous pouvez voir qu'il ya une place dans e tableau. J'essaye de faire une fonction qui fera un rectangle ou une liste de rectangles basés sur le carré. Ainsi, l'exemple reviendriez un rectangle comme

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

Ceci est le code que j'ai maintenant mais DOE pas juste retour quoi que ce soit

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 

De plus, le tableau doit être en mesure d'avoir plus d'un carré.

Answer 1

Voici comment je le ferais:

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 

Notez que:

• hor_ones[r][c] est le nombre de ceux de rang r dans les premières colonnes c.
• ver_ones[c][r] est le nombre de dans la colonne c dans les premières r lignes.

Par conséquent, le nombre de ceux en ligne r et entre les colonnes c1 et c2 (inclus) est:

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

EDIT

Voici ma solution en Java, peut-être est plus facile à comprendre et à implémenter dans 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; 
}