This question is messy, i dont need a working solution, i need some psuedo code.
How would i solve this maze? This is a homework question. I have to get from point green to
red. At every fork i need to 'spawn a thread'
and go that direction. I need to figure out how to get to
red but i am unsure how to avoid paths i already have taken (finishing with any path is ok, i am just not allowed to go in circles).
Heres an example of my problem, i start by moving down
and i see a fork so one goes right
and one goes down (or this thread can take it, it doesnt matter). Now lets ignore
the rest of
the forks
and say
the one going right hits
the wall, goes down, hits
the wall
and goes left, then goes up.
The other thread goes down, hits
the wall then goes all
the way right.
The bottom path has been taken twice, by starting at different sides.
How do i mark this path has been taken? Do i need a lock? Is this
the only way? Is there a lockless solution?
Implementation wise i was thinking i could have
the maze something like this. I dont like
the solution because there is a LOT of locking (assuming i lock before each read
and write of
the haveTraverse member). I dont need to use
the MazeSegment class below, i just wrote it up as an example. I am allowed to construct
the maze however i want. I was thinking maybe
the solution requires no connecting paths
and thats hassling me. Maybe i could split
the map up instead of using
the format below (which is easy to read
and understand). But if i knew how to split it up i would know how to walk it thus
the problem.
How do i walk this maze efficiently?
The only hint i receive was dont try to conserve memory by reusing it, make copies. However that was related to a problem with ordering a list
and i dont think
the hint was a hint for this.
class MazeSegment
{
enum Direction { up, down, left, right}
List<Pair<Direction, MazeSegment*>> ConnectingPaths;
int line_length;
bool haveTraverse;
}
MazeSegment root;
class MazeSegment
{
enum Direction { up, down, left, right}
List<Pair<Direction, MazeSegment*>> ConnectingPaths;
bool haveTraverse;
}
void WalkPath(MazeSegment segment)
{
if(segment.haveTraverse) return;
segment.haveTraverse = true;
foreach(var v in segment)
{
if(v.haveTraverse == false)
spawn_thread(v);
}
}
WalkPath(root);
