Quote:
Originally Posted by Redback
adott egy m*n-es tomb. minden eleme csak 1 vagy 0 lehet. Az 1 jelenti a feketet, 0 a feheret. Hogyan lehet megkeresni leggyorsabban a legnagyobb csak feher (0) mezoket tartalmazó téglalapot? Én úgy gondolkoztam, hogy minden mezőhöz hozzárendeltem egy számot, mégpedig hogy a terület bal felső sarkával alkotott téglalapban hány fekete mező van. Ekkor bármely téglalapban lévő fekete mezők meghatározhatóak mindenféle ciklus nélkül. Ezután meghatározom a terület "területét" (m*n).Mindig csökkentem eggyel a terület értékét, és megkeresem mekkora téglalapoknak annyi a területe, aztán megnézem hogy az eredeti területben belefér-e magassága és szélessége, ha igen, akkor végignézem az összes olyan téglalapot az eredeti területben, és ha csak fehér mezők vannak benne, akkor győzelem. De ez túl lassú  500*500-ra 60 mp alatt kéne lefutni, de csak 3-4 perc alatt fut le |
Szeretem az ilyen feladatokat
Van egy jó ötletem, hogyan lehetne megközelíteni, csináltok egy próbált és elmondom milyen eredményre jutottam, egyébként egy 500x500-as tömb nem akkora adatméret, úgyhogy sztem bőven 1perc alá lehetne vinni.
Egyébkétn a te megközelítésed akkor jó, ha tudni lehet, hogy a keresett téglalap legalább a terület felét-háromnegyedét lefedi, de ha mondjuk egy 2x2 a legnagyobb, akkor szívás mire eljutsz odáig