Thursday, May 26, 2005

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:

At 12:20 AM, Blogger kattricker said...

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.

 
At 1:44 AM, Blogger NGM said...

Hi
The idea of saving the last recursion call seems great.

and nice meeting you as well!
- Narasimha

 
At 6:15 AM, Anonymous Anonymous said...

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

 
At 6:15 AM, Anonymous Anonymous said...

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

 
At 6:15 AM, Anonymous Anonymous said...

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

 
At 6:15 AM, Anonymous Anonymous said...

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

 
At 6:15 AM, Anonymous Anonymous said...

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

 
At 6:15 AM, Anonymous Anonymous said...

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

 
At 6:16 AM, Anonymous Anonymous said...

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

 
At 6:16 AM, Anonymous Anonymous said...

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

 

Post a Comment

<< Home