StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><code>LSBRA(X,Y)</code> means "Largest Square with Bottom-Right At X,Y"</p> <p>Pseudocode:</p> <pre><code>LSBRA(X,Y): if (x,y) == 0: 0 else: 1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) ) </code></pre> <p>(For edge cells, you can skip the MIN part and just return 1 if (x,y) is not 0.)</p> <p>Work diagonally through the grid in "waves", like the following:</p> <pre><code> 0 1 2 3 4 +---------- 0 | 1 2 3 4 5 1 | 2 3 4 5 6 2 | 3 4 5 6 7 3 | 4 5 6 7 8 </code></pre> <p>or alternatively, work through left-to-right, top-to-bottom, as long as you fill in edge cells.</p> <pre><code> 0 1 2 3 4 +---------- 0 | 1 2 3 4 5 1 | 6 7 8 9 . 2 | . . . . . 3 | . . . . . </code></pre> <p>That way you'll never run into a computation where you haven't previously computed the necessary data - so all of the <code>LSBRA()</code> "calls" are actually just table lookups of your previous computation results (hence the dynamic programming aspect).</p> <p><strong>Why it works</strong></p> <p>In order to have a square with a bottom-right at X,Y - it must contain the overlapping squares of one less dimension that touch each of the other 3 corners. In other words, to have</p> <pre><code>XXXX XXXX XXXX XXXX </code></pre> <p>you must also have...</p> <pre><code>XXX. .XXX .... .... XXX. .XXX XXX. .... XXX. .XXX XXX. .... .... .... XXX. ...X </code></pre> <p>As long as you have those 3 (each of the LSBRA checks) N-size squares plus the current square is also "occupied", you will have an (N+1)-size square.</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