Maze and matrix
Hi
I'm a beginner . I have a problem for find a path in maze .
I have a matrix for example (6X5) .
*** *
*
****
****
****
****
. I want find a path in matrix . I don't have information about stack , graph theory , and recursive function .How can I find a path ????
I'm a beginner . I have a problem for find a path in maze .
I have a matrix for example (6X5) .
*** *
*
****
****
****
****
. I want find a path in matrix . I don't have information about stack , graph theory , and recursive function .How can I find a path ????
It must be called "wave algorithm".
Create another matrix of the same size, fill it with (-1)s.
Put 0 in the start point. Than look around and where there is (-1), put 1. So, the cells with value 1 are 1 step from the starting point.
Look at each cell with value 1, and all "not-yet-looked" neighbour cells (with (-1)) put value 2. ...When you finish, you will have the map showing for how many steps you can move from starting point to a given point.
The path is restored in quite a simple way: from a destination cell with number N in it go to any cell with (N-1) value. From it - go to a cell with (N-2) value... until you come to 0-valued cell (starting point).
Create another matrix of the same size, fill it with (-1)s.
Put 0 in the start point. Than look around and where there is (-1), put 1. So, the cells with value 1 are 1 step from the starting point.
Look at each cell with value 1, and all "not-yet-looked" neighbour cells (with (-1)) put value 2. ...When you finish, you will have the map showing for how many steps you can move from starting point to a given point.
The path is restored in quite a simple way: from a destination cell with number N in it go to any cell with (N-1) value. From it - go to a cell with (N-2) value... until you come to 0-valued cell (starting point).
Ops, it is called "Lee algorithm" in english.
http://en.wikipedia.org/wiki/Lee_algorithm
http://en.wikipedia.org/wiki/Lee_algorithm
Topic archived. No new replies allowed.