CODEWITHSUNDEEP
c++recursion
Paul
Paul

Reputation: 13

Recursively finding a path through a maze c++

I have been working to solve this for hours now. I am looking to use a recursive function to solve a maze that is given by the user input. The structure of the maze looks like this:

##########          
#  ###   #
#  #     #
#        #
#    o   #
#        #
##########   

        bool searchMaze(int currR, int currC)
        if (currR > (rows-1) || currC > (columns-1) || currR < 0 || currC < 0)
            return false;
        if (maze[currR][currC] == "o")
            return true;
        if (maze[currR][currC] == "#")
            return false;
        maze[currR][currC] = "+";

        if (searchMaze((currR - 1), currC) == true)
        {
            return true;
        }
        if (searchMaze(currR, (currC + 1)) == true)
        {
            return true;
        }

        if (searchMaze((currR + 1), currC) == true)
        {
            return true;
        }
        if (searchMaze(currR, (currC - 1)) == true)
        {
            return true;
        }
        maze[currR][currC] = " ";
        return false;
    }

This is my recursive method above and the "o" marks a solution. Every time I run the program I am facing an infinite recursion and get the error

"Exception thrown at 0x002396DA in projectName.exe: 0xC0000005: Access violation writing location 0x000A0FFC" and "Unhandled exception at 0x002396DA in projectName.exe: 0xC0000005: Access violation writing location 0x000A0FFC."

Upvotes: 1

Views: 1707

Answers (2)

eesiraed
eesiraed

Reputation: 4654

You never checked if you are looking at a spot that you have already explored before. You set the current path to "+"s, but you never actually checked for it in the function. Add an if statement to have the function not recurse if the current position is marked "+".

By the way, you can speed up your algorithm a lot by not setting the path back to " " when you backtrack so that once a position is explored you don't ever come back to it. This works because it does not matter where you came from, it only matters if there is a path starting from that position.

Upvotes: 1

Gyapti Jain
Gyapti Jain

Reputation: 4106

Add the missing case:

if (maze[currR][currC] == "+")
    return false;  // Already visited

You are tracing back the already visited trail and making no use of '+' marks traced by you causing the infinite recursion and the iterations are not converging.

Upvotes: 5

Related Questions