23. Největší obdélník

Máme tvar pozemku (přesněji, tvar zastavitelné oblasti) nakreslený jako černobílý obrázek a chceme vědět, jak velký dům se tam dá postavit. Abychom si to nekomplikovali, tak dům musí mít vždycky tvar obdélníka zarovnaného s osami souřadnic, čili nebude nijak natočený. Velikost domu měříme jeho plochou, jinak nejsou žádná omezení.

Vstupem programu je rastrový obrázek z černé a bílé. Je zapsaný jako pole polí jedniček a nul, čili vstup je pole, jehož každým prvkem je pole, které obsahuje jen jedničky a nuly.

Výstupem programu je jedno číslo, a to největší možná plocha obdélníka, který obsahuje výhradně jedničky.

Není potřeba podrobně určovat, kde ten největší obdélník najdeme – protože se dá čekat, že takové podrobnosti by v případě potřeby bylo už docela snadné přidat. Nemusíte řešit rychlost, stačí, když ten program vždycky dá správný výsledek.

Rada: nevymýšlejte žádné fikanosti, použijte hrubou výpočetní sílu.