Cerchio BAS

rem *** implementa Dijkstra
1000 print chr$(147);
1010 s=ti

rem *** Caricamento Matrice in c(x,y)
1020 dim c(23,23)
1030 for i=1 to 23
1040 for j=1 to 23
1050 read c(j,i)
1060 next
1070 next

rem *** direzioni
1080 a$(1)="n ": a$(2)="ne": a$(3)="e ": a$(4)="se"
1090 a$(5)="s ": a$(6)="so": a$(7)="o ": a$(8)="no"

rem *** l(): array dei nodi raggiungibili da (12,12)
rem *** v(): array dei nodi visitati
rem *** z ultimo nodo dell'array
rem *** w nodo corrente dell'array
rem *** f numero di nodi finali trovati
1100 dim l(385,4), v(23,23)
1110 l(1,1)=12: l(1,2)=12: l(1,4)=0: l(1,3)=0: v(12,12)=1
1120 x=12: y=12: z=1: w=1: f=1
rem *** l(1)= coord X
rem *** l(2)= coord Y
rem *** l(3)= direzione dal nodo precedente
rem *** l(4)= indice del nodo precedente

rem *** d: valore di distanza del nodo corrente
rem *** xp,xm,yp,ym: coordinate raggiungibili dal nodo corrente
1130 d=c(x,y): if d=10 goto 1710
1140 xp=x+d: xm=x-d: yp=y+d: ym=y-d

rem *** NORD
rem *** se la coordinata verticale è fuori misura passa a SE
rem *** se il nodo destinatario è già visitato o è fuori cerchio passa a NE
rem *** se il nodo precedente adiacente è finale allora passa a NE
rem *** se il nodo è finale va a stampare il percorso
1150     if ym < 1 goto 1290
1170 if v(x,ym)=1  goto 1220
1180 if c(x,ym)=0  goto 1220
1190 if c(x,ym+1)=10 goto 1220
1200 z=z+1: l(z,1)=x : l(z,2)=ym: l(z,4)=w: l(z,3)=1: v(x,ym)=1
1210 if c(x,ym)=10 then gosub 1980

rem *** NORDEST
1220     if         xp >23 goto 1430
1240 if v(xp,ym)=1  goto 1290
1250 if c(xp,ym)=0  goto 1290
1260 if c(xp-1,ym+1)=10 goto 1290
1270 z=z+1: l(z,1)=xp: l(z,2)=ym: l(z,4)=w: l(z,3)=2: v(xp,ym)=1
1280 if c(xp,ym)=10 then gosub 1980

rem *** EST
1290     if         xp >23 goto 1430
1310 if v(xp,y)=1 goto 1360
1320 if c(xp,y)=0  goto 1360
1330 if c(xp-1,y)=10 goto 1360
1340 z=z+1: l(z,1)=xp: l(z,2)=y : l(z,4)=w: l(z,3)=3: v(xp,y)=1
1350 if c(xp,y)=10 then gosub 1980

rem *** SUDEST
1360     if yp >23  goto 1570
1380 if v(xp,yp)=1 goto 1430
1390 if c(xp,yp)=0 goto 1430
1400 if c(xp-1,yp-1)=10 goto 1430
1410 z=z+1: l(z,1)=xp: l(z,2)=yp: l(z,4)=w: l(z,3)=4: v(xp,yp)=1
1420 if c(xp,yp)=10 then gosub 1980

rem *** SUD
1430     if yp >23 goto 1570
1450 if v(x,yp)=1 goto 1500
1460 if c(x,yp)=0 goto 1500
1470 if c(x,yp-1)=10 goto 1500
1480 z=z+1: l(z,1)=x : l(z,2)=yp: l(z,4)=w: l(z,3)=5: v(x,yp)=1
1490 if c(x,yp)=10 then gosub 1980

rem *** SUDOVEST
1500     if         xm < 1 goto 1710
1520 if v(xm,yp)=1 goto 1570
1530 if c(xm,yp)=0 goto 1570
1540 if c(xm+1,yp-1)=10 goto 1570
1550 z=z+1: l(z,1)=xm: l(z,2)=yp: l(z,4)=w: l(z,3)=6: v(xm,yp)=1
1560 if c(xm,yp)=10 then gosub 1980

rem *** OVEST
1570     if         xm < 1 goto 1710
1590 if v(xm,y)=1 goto 1640
1600 if c(xm,y)=0 goto 1640
1610 if c(xm+1,y)=10 goto 1640
1620 z=z+1: l(z,1)=xm: l(z,2)=y : l(z,4)=w: l(z,3)=7: v(xm,y)=1
1630 if c(xm,y)=10 then gosub 1980

rem *** NORDOVEST
1640     if ym < 1  goto 1710
1660 if v(xm,ym)=1 goto 1710
1670 if c(xm,ym)=0 goto 1710
1680 if c(xm+1,ym+1)=10 goto 1710
1690 z=z+1: l(z,1)=xm: l(z,2)=ym: l(z,4)=w: l(z,3)=8: v(xm,ym)=1
1700 if c(xm,ym)=10 then gosub 1980

rem *** va al prossimo nodo, se non siamo oltre la fine...
1710 w=w+1: x=l(w,1): y=l(w,2): if w<=z goto 1130

rem *** chiusura
1720 print "tempo di calcolo: " (ti-s)/60 "sec";
1730 get b$: if b$="" then 1730
1740 end

1750 data 0,0,0,0,0,0,0,0,0,0,10,10,10,0,0,0,0,0,0,0,0,0,0
1760 data 0,0,0,0,0,0,0,10,10,10,4,7,7,10,10,10,0,0,0,0,0,0,0
1770 data 0,0,0,0,0,10,10,5,4,4,8,3,3,4,6,3,10,10,0,0,0,0,0
1780 data 0,0,0,0,10,1,4,5,1,1,1,4,5,1,7,1,3,5,10,0,0,0,0
1790 data 0,0,0,10,4,9,4,9,6,7,5,5,5,8,7,6,6,8,5,10,0,0,0
1800 data 0,0,10,3,7,2,9,8,3,5,6,7,3,9,1,8,7,5,8,5,10,0,0
1810 data 0,0,10,1,4,7,8,4,2,9,2,7,1,1,8,2,2,7,6,3,10,0,0
1820 data 0,10,7,2,1,8,5,5,3,1,1,3,1,3,3,4,2,8,6,1,3,10,0
1830 data 0,10,4,2,6,7,2,5,2,4,2,2,5,4,3,2,8,1,7,7,3,10,0
1840 data 0,10,4,1,6,5,1,1,1,9,1,4,3,4,4,3,1,9,8,2,7,10,0
1850 data 10,4,3,5,2,3,2,2,3,2,4,2,5,3,5,1,1,3,5,5,3,7,10
1860 data 10,2,7,1,5,1,1,3,1,5,3,3,2,4,2,3,7,7,5,4,2,7,10
1870 data 10,2,5,2,2,6,1,2,4,4,6,3,4,1,2,1,2,6,5,1,8,8,10
1880 data 0,10,4,3,7,5,1,9,3,4,4,5,2,9,4,1,9,5,7,4,8,10,0
1890 data 0,10,4,1,6,7,8,3,4,3,4,1,3,1,2,3,2,3,6,2,4,10,0
1900 data 0,10,7,3,2,6,1,5,3,9,2,3,2,1,5,7,5,8,9,5,4,10,0
1910 data 0,0,10,1,6,7,3,4,8,1,1,1,2,1,2,2,8,9,4,1,10,0,0
1920 data 0,0,10,2,5,4,7,8,7,5,6,1,3,5,7,8,7,2,9,3,10,0,0
1930 data 0,0,0,10,6,5,6,4,6,7,2,5,2,2,6,3,4,7,4,10,0,0,0
1940 data 0,0,0,0,10,2,3,1,2,3,3,3,2,1,3,2,1,1,10,0,0,0,0
1950 data 0,0,0,0,0,10,10,7,4,4,5,7,3,4,4,7,10,10,0,0,0,0,0
1960 data 0,0,0,0,0,0,0,10,10,10,3,3,4,10,10,10,0,0,0,0,0,0,0
1970 data 0,0,0,0,0,0,0,0,0,0,10,10,10,0,0,0,0,0,0,0,0,0,0

rem *** stampa il percorso trovato (all'indietro)
1980 print "soluzione "; f: print" ^  *fine*   ";
1990 k=z: f=f+1
2000 p=l(k,1): q=l(k,2)
2010 if c(p,q)<10 then print "per"c(p,q)"passi da";
2020 print " ("mid$(str$(p),2);",";mid$(str$(q),2)")"
2030 print" "+chr$(125)+"  ";a$(l(k,3));" ";
2040 k=l(k,4): if k>1 goto 2000
2050 print "per"c(12,12)"passi da (12,12)":print
2060 return