For this program we are trying to solve a maze using recursion but im having tro

Question

For this program we are trying to solve a maze using recursion but im having trouble getting it to work.

boolean solveMaze(int r, int c)

{

if (current cell is outside the maze)

return false

if (current cell is the exit)

return true

if (current cell not open)

return false

Mark (with a +) current cell as part of the solution path

if (solveMaze(cell below the current cell) == true)

return true

if (solveMaze(cell to the right of the current cell) == true)

return true

if (solveMaze(cell to the left of the current cell) == true)

return true

if (solveMaze(cell above the current cell) == true)

return true

Unmark (with an x) current cell as part of the solution path

return false

}

This is what i have at the moment and i cant figure out what I'm doing wrong

public boolean solveMaze(int r, int c)
    {
        boolean solved = false;

if (r < 0 || c < 0 || r >= maze.getRows() || c >= maze.getColumns())
        {
            return solved;
        }
        if (maze.isExit(r, c))
        {
            solved = true;
            return solved;
        }
        if (maze.isOpen(r, c) == false)
        {
            solved = true;
            return solved;
        }
        if (solveMaze(r + 1, c) == true)
        {
            maze.setCell(r, c, 'X');
            if(solveMaze(r + 1, c)){
                //maze.printMaze();
                steps++;
                solved = true;
                return solved;
            }
            maze.setCell(r, c, '+');
        }
        if (solveMaze(r, c + 1) == true)
        {
            maze.setCell(r, c, 'X');
            if(solveMaze( r, c + 1)){
                //maze.printMaze();
                steps++;
                solved = true;
                return solved;
            }
            maze.setCell( r, c, '+');
        }
        if (solveMaze(r, c - 1) == true)
        {
            maze.setCell( r, c, 'X');
            if(solveMaze( r, c - 1)){
                //maze.printMaze();
                steps++;
                solved = true;
                return solved;
            }
            maze.setCell(r, c, '+');
        }
        if (solveMaze(r - 1, c) == true)
        {
            maze.setCell(r, c, 'X');
            if(solveMaze(r - 1, c)){
                //maze.printMaze();
                steps++;
                solved = true;
                return solved;
            }
            maze.setCell(r, c, '+');
        }
        return solved;
    }

Explanation / Answer

I considered the start position will be 0,1 and, the maze size will be 5 x 5

In your case you considered the maze always has a solution, if it doesn't have a solution, the program will run into stack overflow.

#include <fstream.h>

using namespace std;

char maze [6][6] = {{0}};
char bmaze [6][6] = {{0}};

ifstream fin ("maze.in");
ofstream fout ("maze.out");

int solution_count = 1;

bool solved;
short e_row, e_col;

void GO(int r, int c)
{
if ( solved )

return;

else if ( r == 5 || c == 5 || r < 0 || c < 0 )

return;

else if ( maze[r][c] == 'x' || bmaze[r][c] == 4 )

return;

else if ( maze[r][c] == 'e' ){

solved = true;
e_row = r;
e_col = c;

solution_count ++;
return;
}

GO(r+1, c);
bmaze[r][c] ++;

GO(r, c+1);
bmaze[r][c] ++;

GO(r, c-1);
bmaze[r][c] ++;

GO(r-1, c);
bmaze[r][c] ++;
}


int main()
{
int size = 5;

int i;
for(i=0 ;i <5;i++)
fin.getline(maze[i], 80);

GO(0, 1);

fout << solved << endl;
fout << e_row << "," << e_col << endl;
fout << solution_count << endl;

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.