Dykuma
Taškai: 6
Lukas keliauja aplink pasaulį. Aplankęs daug vaizdingų vietovių, pasiekė dykumą. Kelionę per dykumą pradeda langelyje A1 ir turi pasiekti palmę langelyje D3. Lukas gali eiti kairėn, dešinėn, aukštyn ir žemyn, bet negali eiti įstrižai. Per tą patį langelį gali eiti tik kartą. Taip pat turi vengti langelių su kaktusu.
Lukas turi rinkti langeliuose esančius obuolius ir vandens lašus. Pereinant iš vieno langelio į kitą netenkama vieno lašo vandens ir vieno obuolio. Jei Lukas neturi vandens ir obuolio, nebegali toliau keliauti.
Pavyzdyje geltona spalva pažymėtas teisingas dykumos perėjimo kelias:
A1: turi 3 lašus ir 1 obuolį A2: liko 2 lašai ir 2 obuoliai A3: liko 1 lašas ir 1 obuolys B3: liko 1 lašas ir 2 obuoliai C3: liko 1 lašas ir 1 obuolys D3: tikslas pasiektas! |
Padėkite Lukui pereiti dykumą ir pasiekti langelį su palme.
Yra du galimi keliai: vienas pavaizduotas paveiksle, kitas toks pat, tik dar aplankant E5 ir E6. Visuose kituose keliuose pritrūktų vandens arba obuolių.
-----
Užduotis remiasi gerai žinomu informatikos mokslo paieškos į gylį algoritmu.
Paieška į gylį (angl. depth-first search, DFS) – paieškos grafe arba grafo apėjimo būdas, kai pasirinkus pradinę viršūnę einama grafo briaunomis kiek įmanoma giliau, renkantis vis naują viršūnę; kai paskutinė aplankyta viršūnė naujos (dar neaplankytos) kaimynės nebeturi, tada grįžtama iki artimiausios neaplankytos briaunos ir vėl ieškoma kuo giliau tol, kol bus rastas ieškomas tikslas arba kol bus aplankytos visos grafo viršūnės ir briaunos.
Šis uždavinys reikalauja gebėjimo atlikti kelias užduotis vienu metu. Daugelio užduočių atlikimas vienu metu yra tiek žmogaus gebėjimas, tiek kompiuterio funkcija. Tokio sprendimo ieškojimas reikalauja vienu metu apdoroti kelis susijusius kintamuosius.
Užduotis interaktyvi. Pateikiamas žemėlapis arba į teksto laukelį įrašomos langelių, kuriuos Lukas praeina, koordinatės.