Computador doméstico. Labirinto
Nesta ocasión, realizaremos un programa que axudará á xagua a buscar a saída ao labirinto. Este programa está escrito paira Tee vídeo, pero tamén se pode escribir paira spectrum.
Sinalaremos o labirinto mediante unha matriz. Os obstáculos indicaranse cun "1" e as celas libres cun "Ø".
A entrada ao labirinto (1,1) será o inerte e a saída (m, n) será a dimensión do inerte, m e n. Neste caso utilizaremos m=n=8.
O rato definirase coa súa posición, é dicir, coas coordenadas do punto ou pila que se atopa no momento. Toma nota do que sempre estará nunha pila Ø. Ademais, hai que definir as posibles directrices que pode ter o pano. As direccións posibles son oito en todas as celas, excepto nas de bordo. Así que para que o comportamento do xagua sexa igualitario en todos os lugares, rodearemos o labirinto de obstáculos. Ver como:
O cambio de coordenadas que supón cada dirección preséntase na táboa NORANTZA (8,2):
Modificación da coordenada de columnas paira seguir o rumbo I NORANTZA (I,1)
Modificación da coordenada de liña paira seguir a dirección NORANTZA (I,2) I
Xagua partirá da pila de entrada e pasará dun punto a outro fuxindo de obstáculos. Cando non se poida seguir adiante, deberá retroceder. Por tanto, o camiño percorrido polo carreiro condúcenos pola táboa BIDEA (64,3).
En cada un dos campos desta táboa gardarase:
- Coordenadas dunha pila que compón o camiño
- Sentido de paso desta pila a outra
Cando Xagua atópase nunha pila de auga, a sobriedade deberá analizala en busca dun "bo punto". Para que una pila sexa un "bo punto" debe cumprir os seguintes requisitos:
- Ausencia de obstáculos (marcado con Øen a táboa LAB).
- Que a xagua non pase por esta pila (que a MARCA estea marcada con Øen a táboa).
Se atopa entre os oito puntos da zona un punto que cumpra estas condicións, gardaranse as coordenadas da pila actual e a dirección que debe seguir paira pasar ao novo punto e pasarase ao novo punto. Aquí seguirá o mesmo proceso.
Pola contra, si tras analizar os oito puntos da zona non se ve a posibilidade de pasar a ningún punto, deberá retroceder, pasando á primeira pila (a última pila introducida na táboa BIDEA) e desde aquí tentalo noutro sentido. O proceso é repetitivo. Manterase até chegar a unha destas dúas situacións:
- Localización da saída
- Non retroceder
No primeiro caso, o camiño aparecerá marcado en vermello. No segundo, a mensaxe será:
"Non hai camiño!!"
Como poderías comprobar, mencionamos tamén a táboa chamada MARCA. Na seguinte táboa iremos marcando cun "1" paira saber de que cuarto pasou a mocha a medida que a movamos. Se non se fai isto, pódese meter nun abrandamento interminable.
Un exemplo axudarache a comprender mellor: Supoñamos que o modesto (3,7) está na inerte, que o primeiro "bo punto" que empeza a estudar e atopar as celas da zona é o do norte (3,6). (3,7,2 norte) se garda na táboa BIDEA e pásase ao momento (3,6). Aquí fará o mesmo, pero si tras revisar as celas adxacentes non se pode mover, deberá retroceder, é dicir, volver ao momento (3,7) e tentar a seguinte dirección (norantza 3, nordés). Seguir así cando poida seguir adiante e non poida retroceder até chegar á saída ou comprobar que non hai camiño.
Zu idazle
Zientzia aldizkaria
