Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az I. 274. feladat (2011. október)

I. 274. Adott egy n×m-es (1\len,m\le500) 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ó.

(10 pont)

A beküldési határidő 2011. november 10-én LEJÁRT.


Megoldásokról:

Viszonylag sok, teljes értékű megoldás érkezett. A megoldók egy része nem használta a feladat szövegében megfogalmazott ötletet, hogy előre számítsuk ki é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ó.

Többen észrevették, hogy az egyes cellákhoz tartozó fekete négyzetek számát rekurzív módszerrel meg lehet határozni:

Ha (a,b) cella fekete, akkor T(a,b)=T(a-1,b)+T(a,b-1)-T(a-1,b-1)+1. Ha a cella fehér, akkor T(a,b)=T(a-1,b)+T(a,b-1)-T(a-1,b-1).

A T(0,b)=0 és T(a,0)=0, minden a-ra és b-re.

Ha egy téglalap bal felső sarka (a1,b1) és a jobb alsó sarka (a2,b2) és nincs benne fekete cella, akkor: T(a2,b2)=T(a1-1,b2)+T(a2,b1-1)-T(a1-1,b1-1). Az algoritmus egymásba ágyazott ciklusok segítségével mindig egy adott cellából kiinduló téglalapokat vizsgálja, majd a nem fekete cella tartalmúak közül a legnagyobbat választja ki.

Mintamegoldásként Szilágyi Dániel 10. osztályos (Újvidék, Jovan Jovanovic Zmaj Gimnázium) tanuló munkáját közöljük: I274.cpp

A megoldások vizsgálatához használt tesztállományok: teszt.zip

A tesztállományok nevei, egyik legnagyobb téglalap két koordinátája, amely csak fehér cellákat tartalmaz és ennek területe:

be0.txt (6,1) (8,6) 18
be1.txt (4,1) (9,8) 48
be2.txt (1,1) (10,15) 150
be3.txt minden négyzet fekete
be4.txt (76,28) (85,36) 90
be5.txt (55,91) (75,95) 105
be6.txt (225,105) (227,145) 123
be7.txt (225,105) (227,145) 123
be8.txt (337,142) (345,159) 162
be9.txt (120,120) (180,180) 3721

Statisztika:

12 dolgozat érkezett.
10 pontot kapott:Adrián Patrik, Antal János Benjamin, Barkaszi Richárd Miklós, Fényes Balázs, Gema Barnabás, Hoffmann Áron, Jákli Aida Karolina, Kovács Balázs Marcell, Kucsma Levente István.
9 pontot kapott:Varga 256 Erik.
8 pontot kapott:1 versenyző.
5 pontot kapott:1 versenyző.

A KöMaL 2011. októberi informatika feladatai