StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You can do it in <code>O(n^2)</code> relatively easy.<br> First, some-precalculations. For each cell in matrix, calculate how many consecutive cells below it have the same number.<br> For your example, resulting matrix <code>a</code> (couldn't think of better name :/) will look like this</p> <pre><code>0 0 0 0 0 2 2 1 1 2 2 2 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 </code></pre> <p>It can be produced in <code>O(n^2)</code> easily.</p> <p>Now, for each row <code>i</code>, let's find all rectangles with top side in row <code>i</code> (and bottom side in row <code>i + height - 1</code>).<br> Here's an illustration for <code>i = 1</code></p> <pre><code>0 0 0 0 0 0 0 ------------- 4 4 2 2 2 0 0 4 4 2 2 2 0 0 0 0 2 2 2 1 1 ------------- 0 0 0 0 0 1 1 </code></pre> <p>Now, the main idea</p> <pre><code>int current_width = 0; for (int j = 0; j < matrix.width; ++j) { if (a[i][j] < height - 1) { // this column has different numbers in it, no game current_width = 0; continue; } if (current_width > 0) { // this column should consist of the same numbers as the one before if (matrix[i][j] != matrix[i][j - 1]) { current_width = 1; // start streak anew, from the current column continue; } } ++current_width; if (current_width >= width) { // we've found a rectangle! } } </code></pre> <p>In the example above (<code>i = 1</code>) <code>current_width</code> after each iteration will be <code>0, 0, 1, 2, 3, 0, 0</code>. </p> <p>Now, we need to iterate over all possible <code>i</code> and we have a solution.</p>

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