BEBRO konkurso užduotys 2017

 

Sienų naikinimas

Taškai: 12

Labirintą sudaro tušti kambariai (balti kvadratai) ir sienos (pilki kvadratai).

Galima judėti iš vieno tuščio kambario į gretimą tuščią kambarį horizontaliai arba vertikaliai, bet ne įstrižai.

Pažymėkite (spustelėdami) kuo mažiau sienų, kurios turi būti panaikintos, kad būtų galima nueiti iš apatinio kairio kampo į viršutinį dešinį labirinto kampą.

Paaiškinimas
Atsakymas

Mažiausiai reikia panaikinti 3 sienas. Žemiau esančiame paveiksle šios sienos paryškintos raudonai. Žalia linija rodo kelią, kuriuo einama.

Sistemiškai spręsdami šį uždavinį, kiekviename langelyje galime įrašyti skaičių, kiek sienų reikia panaikinti, kad pasiektume šį langelį. Pradėkime nuo apatinio kairio kampo ir kilkime stulpeliu aukštyn. Kadangi šis pirmas langelis yra tuščias, įrašome 0. Antrame langelyje yra siena, todėl jame rašome 1. Kiekviename žingsnyje, jei langelyje yra siena, pridedame prie turimo skaičiaus vienetą, o jei tai – tuščias kambarys, paliekame turimą skaičių.

Tada pereiname į kitą stulpelį. Reikia žiūrėti ir į kairėje, ir į apačioje esančius langelius. Iš tų dviejų langelių išrenkame mažiausią skaičių. Tada, jei langelis turi sieną, turimą skaičių padidiname vienetu, priešingu atveju paliekame turimą skaičių.

Svarbu, kad, įrašydami skaičius, dar turime patikrinti langelius ir priešinga kryptimi (šiuo atveju iš viršaus į apačią ir iš dešinės į kairę) ir perrašyti skaičius taip, kad liktų mažiausias galimas skaičius. Kartais, perrašant skaičius, šie langeliai paveikia ir šalia esančius skaičius. Taigi svarbu kelis kartus patikrinti, ar nereikia keisti skaičių. Žemiau esančiuose paveiksluose langeliai, kuriuose buvo perrašyti skaičiai, nuspalvinti geltonai.

Kai visi langeliai sunumeruojami, matome, kad į finišo langelį įrašytas skaičius 3. Tai reiškia, kad siekiant tikslo reikia panaikinti mažiausiai 3 sienas.

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39