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);
