CODEWITHSUNDEEP
c++recursion
Joshua
Joshua

Reputation: 4320

Recursively escape Maze

Homework, I'm just asking if my logic is sound, and if not, what cases I am missing, not how to do it.

I have an assignment where we had to create a randomly generated maze out of a data file given to us. Each room has is given a number between 1-100 and has (up to) 4 adjacent rooms: North, East, South, and West. A room without an adjacent room will have an adjacent room with a negative identifier. Our "person" is randomly dropped into one of these rooms, and we must find the path out. Outside is designated by a room number of 0.

I have everything but the recursion done, which is almost done. This is my solution:

void Graph::findPath( Room * curRoom )
{
    if( curRoom -> myNumber == 0 )
    //Escaped!
    else
    {
       if( curRoom -> North -> visited == false )
    {   
        curRoom -> visited == true;
        findPath( curRoom -> North )
    }

    if( curRoom -> East -> visited == false )
    {   
        curRoom -> visited == true;
        findPath( curRoom -> East )
    }
    if( curRoom -> South -> visited == false )
    {   
        curRoom -> visited == true;
        findPath( curRoom -> South )
    }
    if( curRoom -> West -> visited == false )
    {   
        curRoom -> visited == true;
        findPath( curRoom -> West )
    }
    }

}

I think I have it correctly. My only concern is that we need to print out the correct path, which I know can be done, but I have no idea how to do it without printing incorrect ones too.

Thank you for your time.

If any information is missing, let me know and I will reply post-haste.

Upvotes: 0

Views: 831

Answers (1)

Jonathan Leffler
Jonathan Leffler

Reputation: 753695

You should probably have the findPath() function return an indication of whether it found a path out of the room rather than always trying all four paths out of the room. (If you find a way out to the North, you don't need to check whether there's also a way out going East, or West, or South.)

You should probably add a room to a list (stack) of 'places on the path' before recursing, removing it before returning if there is no path out from this room. When you get out, this list tells you the path you took.

Upvotes: 1

Related Questions