The recursive solution with newLISP:
Code: Select all
(define (solveMaze matrice sRow sCol eRow eCol)
(local (maze row col visited correctPath starRow startCol endRow endCol)
; matrice labirinto
(setq maze matrice)
; righe della matrice
(setq row (length maze))
; colonne della matrice
(setq col (length (first maze)))
; matrice delle celle visitate
(setq visited (array row col '(nil)))
; matrice soluzione del labirinto
(setq correctPath (array row col '(nil)))
; posizione iniziale: riga
(setq startRow sRow)
; posizione iniziale: colonna
(setq startCol sCol)
; posizione finale: riga
(setq endRow eRow)
; posizione finale: colonna
(setq endCol eCol)
;
; funzione recursive solve
;
(define (recursiveSolve x y)
(catch
(local (return)
;controllo se abbiamo raggiunto la fine e non è un muro
(if (and (= x endRow) (= y endCol) (!= (maze x y) 2))
(throw (setf (correctPath x y) true))
)
; cella muro o cella visitata
(if (or (= (maze x y) 2) (= (visited x y) true)) (throw nil))
; imposta cella come visitata
(setf (visited x y) true)
; controllo posizione riga 0
(if (!= x 0)
; richiama la funzione una riga in basso
(if (recursiveSolve (- x 1) y)
(throw (setf (correctPath x y) true))
)
)
; controllo posizione riga (row - 1)
(if (!= x (- row 1))
; richiama la funzione una riga in alto
(if (recursiveSolve (+ x 1) y)
(throw (setf (correctPath x y) true))
)
)
; controllo posizione colonna 0
(if (!= y 0)
; richiama la funzione una colonna a sinistra
(if (recursiveSolve x (- y 1))
(throw (setf (correctPath x y) true))
)
)
; controllo posizione colonna (col - 1)
(if (!= y (- col 1))
; richiama la funzione una colonna a destra
(if (recursiveSolve x (+ y 1))
(throw (setf (correctPath x y) true))
)
)
return
);local
) ;catch
); recursiveSolve
;
; Chiama la funzione ricorsiva di soluzione
; Se (recursiveSolve startRow startCol) ritorna nil,
; allora il labirinto non ha soluzione.
; Altrimenti la matrice booleana "correctPath"
; contiene la soluzione (valori true).
(if (recursiveSolve startRow startCol) (showPath correctPath))
);local
)
(define (showPath matrix)
(local (row col)
; righe della matrice
(setq row (length matrix))
; colonne della matrice
(setq col (length (first matrix)))
; stampa
(for (i 0 (- row 1))
(for (j 0 (- col 1))
(if (matrix i j) (print " 1") (print " 0"))
)
(println)
)
true
)
)
Example:
; maze (1 = free, 2 = blocked)
1 1 2 1 2 1 1 1 2 1 2 1 2 1 2 2 1 1 1 2
2 1 1 1 2 2 1 1 1 1 1 2 2 1 1 1 1 1 2 2
2 1 2 2 2 2 2 1 1 2 2 2 1 2 2 2 2 1 2 1
2 1 1 1 1 1 2 2 2 1 1 1 1 2 2 2 1 2 1 2
1 2 2 2 2 1 2 2 1 2 1 2 1 2 2 1 1 2 2 2
1 2 2 2 2 1 1 1 1 2 1 2 1 2 2 1 1 2 2 2
1 2 2 2 2 2 2 2 1 2 1 2 1 2 2 1 2 1 2 2
1 2 2 2 2 2 2 2 1 1 1 2 1 2 2 1 1 1 2 2
1 2 2 2 2 2 2 2 1 2 2 2 1 1 1 1 2 1 1 1
1 2 2 2 2 2 2 2 1 2 2 2 1 2 2 1 2 2 2 1
1 2 2 2 2 2 2 2 1 2 2 2 1 2 2 1 2 2 2 1
1 2 2 2 2 2 2 2 1 2 2 2 1 2 2 1 2 2 2 1
; maze definition
; rows
(setq righe 12)
; columns
(setq colonne 20)
; maze matrix
(setq matrice (array righe colonne '(
1 1 2 1 2 1 1 1 2 1 2 1 2 1 2 2 1 1 1 2
2 1 1 1 2 2 1 1 1 1 1 2 2 1 1 1 1 1 2 2
2 1 2 2 2 2 2 1 1 2 2 2 1 2 2 2 2 1 2 1
2 1 1 1 1 1 2 2 2 1 1 1 1 2 2 2 1 2 1 2
1 2 2 2 2 1 2 2 1 2 1 2 1 2 2 1 1 2 2 2
1 2 2 2 2 1 1 1 1 2 1 2 1 2 2 1 1 2 2 2
1 2 2 2 2 2 2 2 1 2 1 2 1 2 2 1 2 1 2 2
1 2 2 2 2 2 2 2 1 1 1 2 1 2 2 1 1 1 2 2
1 2 2 2 2 2 2 2 1 2 2 2 1 1 1 1 2 1 1 1
1 2 2 2 2 2 2 2 1 2 2 2 1 2 2 1 2 2 2 1
1 2 2 2 2 2 2 2 1 2 2 2 1 2 2 1 2 2 2 1
1 2 2 2 2 2 2 2 1 2 2 2 1 2 2 1 2 2 2 1)))
(solveMaze matrice 0 0 11 19)
;-> 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
;-> 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
;-> 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
;-> 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0
;-> 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0
;-> 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0
;-> 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0
;-> 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0
;-> 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1
;-> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
;-> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
;-> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
;-> true