Etxeko ordenadore. Labirintoa

Oraingo honetan, xaguari labirintoko irteera bilatzen lagunduko dion programa egingo dugu. Programa hau Tele video rentzat idatzia dago, baina
spectrum arentzat ere idatz daiteke.

Labirintoa, matrize baten bidez seinalatuko dugu. Oztopoak "1" batez adieraziko dira eta libre dauden gelaskak "Ø" batez.

Labirintoko sarrera (1,1) gelaska izango da eta irteera (m,n) gelaska, m eta n labirintoaren dimentsioak izanik. Kasu honetan, m=n=8 erabiliko dugu.

Xagua bere posizioaz definituko da, hau da, momentuan aurkitzen den puntuaren edo gelaskaren koordenatuaz. Ohar zaitez xagua beti Ø gelaska batean egongo denaz. Honetaz gain, xaguak eduki ditzakeen norantzak definitu behar dira. Norantza posibleak zortzi dira gelaska guztietan, ertzekoetan ezik. Beraz, xaguaren jokaera leku guztietan parekoa izan dadin, labirintoa oztopoz inguratuko dugu. Ikus nola:

Norantza bakoitzak suposatzen duen koordenatu-aldaketa, NORANTZA (8,2) taulan egongo da:

NORANTZA (I,1) I. norantzari jarraitzeko egin behar den
zutabe-koordenatuaren aldaketa

NORANTZA (I,2) I. norantzari jarraitzeko egin behar den
lerro-koordenatuaren aldaketa

Xagua, sarrera-gelaskatik abiatu eta puntu batetik bestera pasatuz joango da oztopoei ihes eginez. Aurrera jarraitu ezinik aurkitzen denean, atzera jo beharko du. Beraz, xaguak ibilitako bidea BIDEA (64,3) taulan gordeaz joango gara.

Taula honen eremu bakoitzean gordeko dena zera da:

Bidea osatzen duen gelaska baten koordenatuak

• Gelaska horretatik beste batera pasatzerakoan jarraitu duen norantza

Xagua gelaska batean dagoenean, inguruko gelaskak aztertu beharko du " puntu on " baten bila. Gelaska batek " puntu ona " izateko baldintza hauek bete behar ditu:

Bertan oztoporik ez egotea (LAB taulan Ø-z markatuta egotea).

• Xagua gelaska horretatik pasa gabe egotea (MARKA taulan Ø-z markatuta egotea).

Inguruko zortzi puntuen artean baldintza hauek betetzen dituen puntu bat aurkitzen badu, uneko gelaskaren koordenatuak eta puntu berrira pasatzeko jarraitu behar duen norantza gorde, eta puntu berrira pasako da. Hemen prozesu berdinari jarraituko dio.

Aldiz, inguruko zortzi puntuak aztertu ondoren inora pasatzeko posibilitaterik ez duela ikusiz gero, atzera jo beharko du; aurreko gelaskara (BIDEA taulan azkena sartutako gelaskara) pasatuz eta hemendik beste norantza batean saiatuz. Prozesua errepikakorra da. Honela jarraituko du bi egoera hauetako batetara iritsi arte:

Irteera aurkitzea

• Atzera jo ezinik gelditzea

Lehenengo kasuan, bidea gorriz markatuta azalduko da. Bigarrenean berriz, ondoko mezua erakutsiko du:

" Ez dago biderik !!! "

Ohartuko zinenez, MARKA izeneko taula ere aipatu dugu. Taula honetan, xagua zein gelaskatatik pasa den jakin ahal izateko "1" batez markatuz joango gara xagua mugitu ahala. Hau egiten ez bada, amaigabeko bigizta batean sar daiteke.

Adibide batez hobeto ulertuko duzu: Demagun xagua (3,7) gelaskan dagoela; inguruko gelaskak aztertzen hasi eta aurkitzen duen lehen " puntu ona " iparraldeko (3,6) dela. (3,7,2 iparraldea ) BIDEA taulan gorde eta (3,6) puntura pasako da. Hemen gauza bera egingo du, baina aldameneko gelaskak aztertu ondoren mugitu ezinik gelditzen bada, atzera jo, hau da, (3,7) puntura itzuli eta hurrengo norantzaz saiatu beharko du (3. norantza, iparrekialdea). Honela segi ahal duenean aurrera jarraituz eta ezin duenean atzera joaz, irteerara irits i edo biderik ez dagoela ohartu arte.