Quote:
Originally Posted by Dus
Én kíváncsi lennék erre az algoritmusra, ha szabad. Érdekelne, mert agyaltam rajta, de nem sok sikerrel.  |
Addig leírom a jelenlegi algoritmus lényegét:
Elindulok a tábla elején, szépen sorfolytonosan haladok. Ha találok egy aktív területet (1) akkor van legalább egy 1x1-es megoldás.
Ezután megnézem, hogy adott irányban (mondjuk X mentén, tehát vízszintesen) meddig találok aktív területet, legyen ez X, utána másik irányban Y. Így tehát van lehetőségem egy maximum X*Y eredményre. Ezt összehasonlítom a korábbi eltárolt legjobb eredménnyel (ha van). Ha az eredményem nagyobb, fölösleges tovább vizsgálni, nem lesz belőle új eredmény. Ezután esetleg végzek még gyorsteszteket (átellenes sarok, oldalak ellenőrzése), amik érvényteleníthetik a jelenlegi keresést, és a legvégén csinálok teljes vizsgálatot (vagyis hogy teljes-e a téglalapom), mivel ez az legidőigényesebb munka. Ha stimmel, és a téglalap nagyobb mint az eddigiek, akkor végeredményként eltárolom, és legközelebb már csak az ennél nagyobb esélyesek vizsgálata történik meg, ami jelentősen csökkenti a futási időt.
Sok helyen lehet ignore feltételeket alkalmazni, pl. ha van egy 10x10-e eredményem, akkor a 491. sor 491. oszlopnál legjobb esetben egy másik 10x10-est találhatok, az ez utáni oszlopokban meg sokkal kisebbeket, ilyenkor ki lehet hagyni a keresést, és következő sorral folytatni (ahol már az utolsó 11 oszlop elhagyható, mivel az is csak 11x9=99 lehetne)
Egyenes rekurzió helyett ajánlott while ciklusokat használni stack műveletek spórolása miatt, sokszor nagyságrendekkel gyorsabb lehet a progi.
Ez a módszer hasonló a tiédhez, vagyis végignézem a táblát, kiszedek belőle max méretű téglalapokat, és feljegyzem a legjobbat, a többi nagy részét pedig keresés előtt is el tudom vetni. De akad más megközelítés is, a reklám után folytatom...