Drėkinimo sistema

Taškai: 6

Bebrai sukūrė išmaniąją laukų drėkinimo sistemą. Vanduo teka iš ežero kalno viršūnėje į 6 laukus apačioje.
Vandens kanaluose bebrai įrengė keturias sklendes, kurias pasukus vanduo gali tekėti tik į kairę arba tik į dešinę.


Kaip reikėtų pasukti sklendes norint drėkinti tik 2, 4, 5 ir 6 laukus?
Spustelėkite juodas rodykles ir perjungsite sklendes.

 

Paaiškinimas

Drėkinimo sistema yra panaši į orientuotąjį grafą. Orientuotas grafas sujungia viršūnes (kanalų susikirtimus) briaunomis (kanalais), kurios yra apibrėžtos krypties (vandens srautas eina nuo viršaus žemyn). Pagal vandens srautą nustatoma, ar apibrėžtos briaunos grafe yra pateiktos, ar ne.
Tam kad nustatytume, kokius laukus laistyti, grafas turi būti pereitas nuo šaknies (ežero) palei visas įmanomas briaunas. Tokiu atveju bus patikrinti visi įmanomi keliai ir pažymėtos visos pasiekiamos briaunos.  Algoritmas, kuriuo tikrinama, vadinamas užpildikliu.

Atsakymas

Teisingas sprendimas gaunamas tada, kai žiūrovų atžvilgiu vandens srautas nukreipiamas šitaip: kairėje esanti viršutinė sklendė pasukama į kairę; žemiau jos esanti sklendė – į dešinę; dešinėje esanti viršutinė sklendė pasukama į dešinę; žemiau jos esanti sklendė – į kairę. Tai yra vienintelis teisingas sprendimas: jei vandens srautas kairėje esančia viršutine sklende būtų nukreiptas į dešinę, tai būtų palaistytas ir trečias laukas . Jei vandens srautas kairėje esančia viršutine sklende būtų nukreiptas į kairę, o žemiau esanti sklendė atsukta į dešinę, tai būtų palaistytas ir pirmas laukas. Analogiškai kai dešinėje esanti viršutinė sklendė pasukama į kairę, tai palaistomas ir trečias laukas. Kai kairėje esanti žemutinė sklendė nukreipiama į dešinė, tai ketvirtas laukas lieka nepalaistytas.

 

Interaktyvi užduotis

 

 
Informacija atnaujinta 2015-12-03 07:50:57