StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is how I would do it:</p> <pre><code>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 </code></pre> <p>Note that:</p> <ul> <li><code>hor_ones[r][c]</code> is the number of ones in row r in the first c columns.</li> <li><code>ver_ones[c][r]</code> is the number of ones in column c in the first r rows.</li> </ul> <p>Therefore, the number of ones in row <code>r</code> and between columns <code>c1</code> and <code>c2</code> (inclusive) is:</p> <p><code>hor_ones[r][c2+1] - hor_ones[r][c1]</code></p> <p><strong>EDIT</strong></p> <p>Here's my solution in Java, maybe it is easier for you to understand and implement in VB.NET:</p> <pre><code>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; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload