Recursive issue

[Dlazyguy]

I have a recursive maze problem here but it marks everything that has a '.' in the matrix as an 'x'. I need it to mark it with '+' when it is part of the path and the 'x' is to show that it is not in the solution path. Any ideas?

  int Maze::SolveMaze(char **a, int x, int y, int row, int col)
{
     
     if ( y < 0 || y > row-1 || x < 0 || x > col-1 ) return false;

     if (a[y][x] != '.')
     return false;
     //marks + if part of the solution path
     a[y][x]='+';
     
     count++;
     if(SolveMaze( a,x,y-1, row, col)==true) return true;//North
     if(SolveMaze( a,x+1,y, row, col)==true) return true;//East
     if(SolveMaze( a,x,y+1, row, col)==true) return true;//South
     if(SolveMaze( a,x-1,y, row, col)==true) return true;//West
     //marks x if not part of the solution path
     a[y][x]='x';
     return false;  
 }
 

Here is the output after it runs the code.


xx-------x----x
-x-------x----x
-x--xxxxxx----x
-x---x---xxxxxx
-x---x---x----x
-xxxxx---x----x
---x--x--x----x
---x--xxxxxxxxx
---x---x------x
x--x---x------x
xxxxxxxxxxx---x
x--x---x--x---x
x--x---x--xxx-x
xxxx--------x-x
x-----------xxx

[ne555]

You are missing the success base case (the one where you reach the end of the path), so your function always fails.

[Dlazyguy]

I tried using a while loop that goes (while !a[col-1][row-1]) but it only does the 1st cell. Or do you mean something like if(a[col-1][row-1] == '.') {cout<<"end found"; return true;}

[joeyparkker]

I too have this problem.

[ne555]

¿cout? ¿what would your function output anything?

if( x==col-1 and y==row-1 ) //reached the lower right cell
   return true;

[Dlazyguy]

Thanks that worked!! I also added in to make the a[col-1][row-1]='+' so it adds that to path. Also, an off topic question but how would I be able to access a global variable in a class?

[ne555]

If you mean a member function, there is no difference, access it just as in a non-member function.
If you are having trouble, post your code so we can see what you are doing.

[Dlazyguy]

Thank you I figured that out a while back and changed up my code a bit. I just have one last hurdle and that is to figure out a way that if a maze had 2 solutions. It would output that it has 2 solutions. For now I only seem to find one, I found other solutions when I changed the order of North, South, East, West but it just looks messy.

Here is the function that I'm trying to change:

int Maze::SolveMaze(char **a, int x, int y, int row, int col, int **b, int c)
{
    
     if (x==row-1 && y==col-1)
     {  if(a[col-1][row-1]!='.')//checks end of maze
        {
           cout<<"Maze has no end"<<endl;
           return false;
           }
           else 
                  a[col-1][row-1]='L';//Marks the path
                  b[col-1][row-1]=c++;//Marks the number of steps in a different array
                  cout<<"End found!"<<endl;
                  return true;
                  }
     if ( y < 0 || y > row-1 || x < 0 || x > col-1 ) return false;//check if it's safe
     
     if (a[y][x] != '.')
     return false;
     a[y][x]='L';// Marks path
     b[y][x]=c;//Marks number of steps in a different array
     c++;

     if(SolveMaze( a,x,y-1, row, col, b, c)==true) return true;//North
     if(SolveMaze( a,x,y+1, row, col, b, c)==true) return true;//South
     if(SolveMaze( a,x+1,y, row, col, b, c)==true) return true;//East
     if(SolveMaze( a,x-1,y, row, col, b, c)==true) return true;//West
     
     
     
     
     a[y][x]='x';//unmarks if not in path, thinking maybe getting rid of this in another function might help
     b[y][x]=1000;//Marks with 1000 in the int array
     return false;
return false;  
 }

[ZeroSploit]

if ( y < 0 || y > row-1 || x < 0 || x > col-1 ) return false;

This might sound alittle retarded, but instead of "OR" did you try using "AND"...

if (y < 0 && y > row-1 || x < 0 && x > col-1) return false;

[Dlazyguy]

"AND" doesn't work with those inequalities causes a whole mess when compiling.

[ZeroSploit]

ohhhhh, my bad......Just trying something alittle different.......I looked at it, and then I kept looking at it (read it back atleast twice (just that one line, and it just didnt sound right at the time).