45 lines
3.6 KiB
Markdown
45 lines
3.6 KiB
Markdown
|
Zadanie
|
||
|
|
|
||
|
|
1A. Bludisko
|
||
|
|
|
||
|
|
Potkan sa vie pohybovať po štvorcoch hore,dole, doprava i doľava. Bludisko je tvorené štvorcovou mriežkou rozmeru N x N. V bludisku sa nachádzajú prekážky vyznačené 'x'. Potkan pri pohybe nesmie naraziť do žiadnej prekážky.
|
||
|
|
Počiatočná pozícia potkana je v ľavom hornom rohu mriežky vyznačená '*'.
|
||
|
|
Vašou úlohou bude zobraziť optimálnu cestu pre potkana v bludisku. Cestu potkana vyznačte '*'.
|
||
|
|
|
||
|
|
Implementujte funkciu:
|
||
|
|
|
||
|
|
int solve_maze(char* maze,int size);
|
||
|
|
|
||
|
|
maze je jednorozmerné pole do ktorého je uložená mriežka po riadkoch za sebou. Na začiatku poľa sa nachádza prvý riadok mriežky, za ním nasleduje druhý a tak ďalej. Spolu sa v poli maze nachádza size * size znakov.
|
||
|
|
Vašou úlohou bude modifikovať pole maze tak, aby ste v ňom vyznačili cestu z bludiska čo sa nachádza v pravom dolnom rohu bludiska.
|
||
|
|
|
||
|
|
Riešenie
|
||
|
|
|
||
|
|
Moja implementácia zahŕňa algoritmus, ktorý postupne prehľadáva cesty v bludisku. Pred začatím si bludisko vo forme jednorozmerného poľa s dlžkou jedného riadka pretvoríme do
|
||
|
|
dvojrozmerného poľa pre ľahšiu manipuláciu so súradnicami v priestore. Samotný algoritmus pozostáva z nekonečného cyklu, v ktorom sa rozhoduje o ďalšom kroku potkana.
|
||
|
|
|
||
|
|
Potkan sa prepína medzi dvoma módmi prehľadávania, t.j. prehľadávanie novej cesty v bludisku alebo vracanie sa k najbližšej križovatke. Do módu prehľadávania sa dostane ak má možnosť
|
||
|
|
urobiť krok na nepreskúmané políčko. Tieto nepreskúmané možné políčka skontroluje na začiatku cyklu, kedy si vyberá smer kroku. Pri nájdení voľného a nepreskúmaného smeru poznačí
|
||
|
|
aktuálnu pozíciu za preskúmanú a posunie sa do nájdeného smeru. Na novej pozícii si poznačí smer, z ktorého prišiel. V prípade, že voľný smer nenájde, prečíta informáciu z ktorého
|
||
|
|
smeru prišiel z aktuálnej pozície a vráti sa na predošlú. Pri vracaní sa po označenej ceste ide o mód vracania sa k najbližšej križovatke.
|
||
|
|
|
||
|
|
Potkan si označuje políčka zanechávaním čísiel na danej pozícií. Každá číslica obsahuje informácie o preskúmaní a smeru pre vrátenie sa. Reprezentácia informácií v čísle vyzerá
|
||
|
|
následovne:
|
||
|
|
|
||
|
|
| 128 | 64 | 32 | 16 | | 8 | 4 | 2 | 1 |
|
||
|
|
|-----|----|----|------------|---|---------------|---------|------|--------|
|
||
|
|
| | | | preskúmané | | prišiel z/zo: | | | |
|
||
|
|
| | | | políčko | | severu | východu | juhu | západu |
|
||
|
|
|
||
|
|
Po urobení kroku dopredu/späť sa porovná aktuálna pozícia s koncovou/štartovnou, pri zhode sa cyklus ukončí. Vrátením sa na štartovnú pozíciu sa riešenie nenašlo, v opačnom prípade
|
||
|
|
z bludiska odstránia pomocné čísla a vyznačí sa cesta.
|
||
|
|
|
||
|
|
Pred pretvorením pomocného dvojrozmerného poľa bludiska do pôvodného tvaru sa ešte skontrolujú redundatné kroky cesty, z ktorých sa vytvoria "skratky" - znázornené na príklade:
|
||
|
|
|
||
|
|
bez kontroly: * x x x s kontrolou: * x x x
|
||
|
|
* * x * x
|
||
|
|
* * x x * x x
|
||
|
|
* x * * * * x * * *
|
||
|
|
* * * x * * * * x *
|
||
|
|
|
||
|
|
znázornená kontrola spočíva v hľadaní štvorcových ciest a odstránením pravej polovice cesty, kedže algoritmus hľadá nové smery kroku v poradí DOPRAVA, DOLE, doľava, dohora.
|