StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I might not understand the question correctly, but let me propose an algorithm that I think kinda hints at solving your problem.</p> <p>Your problem starts with a rectangular greed where squares are <em>free</em> and <em>non-free</em>. From start the <em>free</em> squares are the ones we are going to build walls with, and the <em>non-free</em> squares are the hollow spaces.</p> <ol> <li>Foreach <em>free</em> square do an <em>expansion</em> around that square, and see what is the biggest area that that square can belong to. By <em>expansion</em> I mean going in all directions from that square whilst it's possible to build an area out of <em>free</em> squares. Associate this largest area with the given <em>free</em> square.</li> <li>Select the square that has the largest associated area, and build your merged wall by expanding around that square. Squares that belong to this merge are marked as <em>non-free</em>. If there are no more <em>free</em> squares you are done, else go to step 1. </li> </ol> <p>After you are done, you should have the largest possible blocks of wall grouped together.</p> <p>To clarify, by <em>expansion</em> around a <em>free</em> square I mean taking the hypothetical largest rectangle that can be built starting from the given square in all available directions.</p> <p>The complexity of this algorithm for a rectangle <code>n*m</code> matrix is intuitively around <code>O(n*n*m*m)</code>. In practice i think it'll be quite quick with your data. Note that this algorithm doesn't provide the fewest number of objects, but rather maximizes the sum of all areas (as per your question). I intune that the problem of minimizing the total number of bodies is much more difficult in terms of complexity.</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