Fórum - Találjunk jobb megoldást!

Van egy 5x5-ös négyzetrács alakú jégpálya, amit egy magasított perem vesz körül. A pálya 3 sarokmezőjében 1-1 doboz van, amik pont elfoglalják a teljes sarokmezőket. Egy lépésben egy dobozt valamelyik főirányban megtolhatunk, és az addig csúszik, amíg a peremnek, vagy egy másik doboznak nem ütődik (ha két doboz szomszédos, akkor csak a közös sorukra/oszlopukra merőlegesen mozgathatók). Ezek lényegében a Sokoban szabályai, kivéve, hogy kívülről is lehet tolni, és hogy a dobozok csúsznak.

A feladat az, hogy minél kevesebb lépéssel juttassunk be egy dobozt a pálya közepére. Pótkérdés: mit mondhatunk (2n+1)×(2n+1)-es pálya esetén?

Azt bevállalom, hogy 2x4n-eshez kell legalább n ;-)

Arra is kíváncsi lennék, hogy lehetne belátni vagy cáfolni, hogy korlátlanul nagy sakktáblánál a megoldás egyértelmű meghatározásához korlátlanul sok fal kell.

Kösz, megszenvedtem vele :)

Ugye ez a megoldás is arra épül, hogy a szélén lehet egyértelműen elkezdeni építeni, de semmi se garantálja, hogy egymástól távol eső falakkal ne lehessen kifeszíteni az ábrát. szóval szerintem szgép nélkül reménytelen. (Papíron könnyű belátni, hogy 1 fal nem elég, illetve szerintem a 2-őt is ki lehet izzadni, bár ehhez még nem volt kedvem, de a 3 már elég reménytelennek tűnik.)

Eleve a 4 falas megoldások száma a szimmetriai megfontolások alapján felére csökkenthető. Másrészt ezek nagy része megoldható a triviális lefedéssel. (Azaz először 2*4-es téglalapokra vágjuk az ábrát, majd ezeket lefedjük külön-külön.) mivel 8ilyen téglalap van, ezért ha egy ilyen lefedés van, akkor van több is. Végül azt is ki lehet használni, hogy ha találunk egy megoldást, amiben van egy 2*4-es 2 elemmel lefedett terület fal nélkül, akkor már léphetünk is tovább.

Határozottan ügyes, grat :-)

Egyébként nekem valóban úgy tűnik, hogy ez az öt fal már egyértelműen meghatározza a kitöltést.

Öt falra szerintem reménytelennek tűnik az összes eset végigpróbálgatása, és még négy falra is valami jó haténkony heurisztikus parkettázó kéne, ami előállítja az összes megfelelő lefedést, ezt pedig nem könnyű megcsinálni, ezért nem írta még meg senki a programot.

Csináltam egyet 5 fallal.

Egyébként azt csodálom, hogy még senki nem írta meg a programot, ami kidobja a jó választ. Kár, hogy én nem értek hozzá. :)

Szép megoldás.

Na jó, nem csigázlak tovább titeket: