Representing a tree in C++ - 【StackMirror】|algorithm|tree|maze

For dynamic programming, what are some of the ways that I store a tree with?

I am working on an assignment that requires me to solve a maze with no left turn and a minimize right turn. The idea that I had is to store all possible paths into a tree and then going through (traverse) the tree looking for the minimum right-turns. To make the code more efficient, anytime a path involves either

a) a left turn b) a solution with more right turn than the current best known solution

I will not add it to the tree. Hopefully I have a clear understanding of what I am doing here. I really do appreciate input on this.

The tree that I am looking at storing will contain all possible directions in the maze, and the parent of each children will be the previous location. I believe that some parents will have more than 2 children.

I am wondering what is the best way to store this kind of tree?

Thank you in advance.

2012-04-04 07:51
by michcs

do you have to save the tree or solve the maze - WeaselFox 2012-04-04 08:05

Oh yes, I do. I am just wondering what's the best way to store the tree. I am just confused/clueless since I've only dealt with trees with only 2 children - michcs 2012-04-04 13:05

Can't you just adapt flood fill or BFS - foxx1337 2012-04-04 14:14

If the problem is to solve the maze, I suggest using backtracking instead of creating such a tree. If you have to create the tree, you could use a tree in which every junction where you could turn right is represented as a node, and the children would be the next junction if turned right, or the next one if you did not. I'm not sure I understood you correctly, but I hope this gives you some pointers as to how to continue.

2012-04-04 13:12
by WeaselFox