### Maze – finding out the way: part 2

Here is one of the possible solutions which I had programmed earlier:

The first step is to find out a suitable representation. One way we can represent the maze is by a graph. The graph includes only the blocks which are not 'filled':

Now how do your build this tree?

- The node (x,y) can be linked to any/all of the following nodes:

(x-1,y), (x+1,y), (x,y-1), (x,y+1).

- Build the tree with only the blocks that are not 'filled' and with the conditions:

(x+1) < MAX blocks & (x-1) >= 0 & (y+1) < MAX blocks & (x-1) >=0

How to find out the path?

- Find out the shortest path from (0,0) to (6,6) using 'shortest path algorithms'

(as balbir and Gopal had pointed out: backtracking/recursion)

Your thoughts?

## 10 Comments:

I think backtracking is pretty much what we can use in this case. Shortest path algorithms work on weights for each route right? I am wondering if we can determine by some means that a path will lead to a dead end. I could implement a one step look ahead to save the last recursion call (i.e. just before banging to a dead end). Any other thoughts?

Oh btw, I am Balbir's friend. Nice to meet you Narsimha.

Hi

The idea of saving the last recursion call seems great.

and nice meeting you as well!

- Narasimha

台北酒店 酒店兼差 酒店兼職 酒店

酒店兼差 酒店兼職 酒店 台北酒店

酒店兼職 酒店 台北酒店 酒店兼差

酒店 台北酒店 酒店兼差 酒店兼職

酒店經紀 酒店打工 酒店工作 酒店上班

酒店經紀 酒店打工 酒店工作 酒店上班

酒店經紀 酒店打工 酒店工作 酒店上班

酒店經紀 酒店打工 酒店工作 酒店上班

Post a Comment

<< Home