Search for squares in an array

Question

I have a 2 dimensional array that is filled with 1s and 0s, for example

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 

You can see that there is a square in the array. I am trying to make a function that will make a rectangle or list of rectangles based on a square. Thus, the example will return a rectangle, for example

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

This is the code I have now, but it just returns nothing

 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 

Also, the array must have more than one square.

Answer 1

Here's how I do it:

 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 

Note that:

• hor_ones[r][c] - the number in row r in the first columns of c.
• ver_ones[c][r] - the number of columns c in the first r rows.

Therefore, the number of rows in row r and between columns c1 and c2 (inclusive):

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

EDIT

Here is my Java solution, it may be easier for you to understand and implement in 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; }