od hlupaco » 6. 6. 2016 18:14
Theseus, Minotaur a Ariadna v labyrintu, plus vtipné lore proč se snaží každý vyhnout každému
V labyrintu je maximálně 100 místností, na vstupu jsou v podstatě hrany (seznam chodeb místnost - místnost), počáteční místnost a koncová místnost pro každou postavu zvlášť.
Každá postava projde za 1 minutu 1 chodbu, nebo se může rozhodnout minutu čekat.
To, že se nechtějí potkat zahrnuje, že se nechtěji ani vidět, tj nesmí se nacházet v jednu minutu ve dvou sousedních místnostech.
Úkol je zkrátka jen vrátit číslo jako nejnižší počet minut za který se mohou každý dostat do cíle se zachováním výše uvedených pravidel.
Paměť 512 kB.
Na ústní už asi nepůjdu protože jsem nedal zápočet ^^ Ale kdybych se tam ještě stavil, připíšu nějaké dojmy odtud.
Řešil jsem to BFS - nejkratší cesta, pak lokalizace prvního konfliktu co nastane, jeho vyřešení, nové BFS odtud a opět řešení prvního konfliktu pokud nějaký je, plus každé řešení konfliktu vyvolá až 3 faktoriál nových BFS větví, protože vždy zkusím dávat přednost postavám v jiném pořadí abych je vyzkoušel všechny. Zde se mi to rozdělí doufám nanejvýš 6krát (kromě případu kdy dva půjdou za sebou a narazí na třetího později, který je potřeba zvlášť ošetřit), a BFS na neohodnocených hranách je O(n) -> cca 600 kroků je pořád úplně cajk, pointa je že bude dost narůstat konstanta s tím ověřováním kdo kdy blokuje jakou místnost
Na druhou stranu se každá postava s každou dostanou do konfliktu nanejvýš jednou, protože všechny chodby jsou obousměrné a projde nimi každý.
Vim že to řešení je silně krkolomný, pokud ste někdo udělal něco hezčího dejte vědět.
Theseus, Minotaur a Ariadna v labyrintu, plus vtipné lore proč se snaží každý vyhnout každému :-)
V labyrintu je maximálně 100 místností, na vstupu jsou v podstatě hrany (seznam chodeb místnost - místnost), počáteční místnost a koncová místnost pro každou postavu zvlášť.
Každá postava projde za 1 minutu 1 chodbu, nebo se může rozhodnout minutu čekat.
To, že se nechtějí potkat zahrnuje, že se nechtěji ani vidět, tj nesmí se nacházet v jednu minutu ve dvou sousedních místnostech.
Úkol je zkrátka jen vrátit číslo jako nejnižší počet minut za který se mohou každý dostat do cíle se zachováním výše uvedených pravidel.
Paměť 512 kB.
Na ústní už asi nepůjdu protože jsem nedal zápočet ^^ Ale kdybych se tam ještě stavil, připíšu nějaké dojmy odtud.
Řešil jsem to BFS - nejkratší cesta, pak lokalizace prvního konfliktu co nastane, jeho vyřešení, nové BFS odtud a opět řešení prvního konfliktu pokud nějaký je, plus každé řešení konfliktu vyvolá až 3 faktoriál nových BFS větví, protože vždy zkusím dávat přednost postavám v jiném pořadí abych je vyzkoušel všechny. Zde se mi to rozdělí doufám nanejvýš 6krát (kromě případu kdy dva půjdou za sebou a narazí na třetího později, který je potřeba zvlášť ošetřit), a BFS na neohodnocených hranách je O(n) -> cca 600 kroků je pořád úplně cajk, pointa je že bude dost narůstat konstanta s tím ověřováním kdo kdy blokuje jakou místnost :-)
Na druhou stranu se každá postava s každou dostanou do konfliktu nanejvýš jednou, protože všechny chodby jsou obousměrné a projde nimi každý.
Vim že to řešení je silně krkolomný, pokud ste někdo udělal něco hezčího dejte vědět.