2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

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.

Paaiškinimas

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.

Atsakymas

Užduotis interaktyvi. Pateikiamas žemėlapis arba į teksto laukelį įrašomos langelių, kuriuos Lukas praeina, koordinatės.

Interaktyvi užduotis