Feladat: I.274 Korcsoport: - Nehézségi fok: -
Füzet: 2011/október, 418 - 419. oldal  PDF  |  MathML 
Témakör(ök): Programozás, algoritmusok

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Adott egy n×m-es (1≤n,m≤500) téglalap alakú terület, amely fekete és fehér négyzetekből áll. Keressük meg ebben azt a legnagyobb téglalapot, amely csak fehér cellákat tartalmaz. Az eredményt a téglalap bal felső és jobb alsó sarkának a koordinátáival és a területével adjuk meg.

 
 

Érdemes meggondolni, hogy n és m viszonylag kis értéke mellett használható módszer, hogy az összes koordináta-párral meghatározott valamennyi téglalap fekete cella-mentességét egymásba ágyazott ciklusokkal ellenőrizzük, majd ezekből a maximális területűt kiválasztjuk. Az összehasonlítások száma az elemek számának negyedik hatványával lesz arányos és ez a futási időt az elemszám növelésével rendkívül megnöveli.
Megoldási ötlet: Számítsuk ki előre és tároljuk el minden cellához, hogy a terület bal felső sarkával együtt téglalapot alkotva hány fekete cellát tartalmaz.
 
 

Az így előkészített értékekkel két koordináta-párral megadott téglalap fekete cella-tartalma ciklusok nélkül kiszámítható.
Készítsünk programot i274 néven, amely meghatározza a legnagyobb téglalapot, amely csak fehér cellákat tartalmaz.
A program a terület nagyságát és a cellák színét (0: fehér és 1: fekete) fájlból olvassa be. A fájl első sora a sorok számát (n) és az oszlopok számát (m) adja meg. Az ezt követő n darab sorban szereplő m darab érték, a példa szerint szóköz elválasztása nélkül, pedig a megfelelő cellák állapotát (0 vagy 1) írja le.
Az eredményt, azaz a téglalap bal felső és jobb alsó sarkainak koordinátáit és a téglalap területét a képernyőn jelenítjük meg. A program egyetlen parancssori argumentuma a bemeneti fájl legyen. A program futtatási ideje maximum 60 másodperc a tesztelésre használt 2.40 GHz, Core2Duo processzorú számítógépen.
 
 

Beküldendő egy tömörített i274.zip állományban a program forráskódja (i274.pas, i274.cpp, ...) és a program rövid dokumentációja (i274.txt, i274.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.