maze pathfinder looping forever

[GonlyG]

I borrowed a recursive maze path finder algorithm with the same logic as a working program, but can't figure out why it exceeds run time (the logic claims it's quite efficient)

I'm given a maze where @ is at start (0,0) and walls are "X", paths are "+", exit is at row, column marked as "$". You cannot revisit a place you already visited.

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;


  const char WALL = 'X';
  const char PATH = '+';
  const char TEMPORARY = '0'; 
  const char MOVE = 'M';
  // return how many paths found
  
int find_maze_path(vector<vector<char>> grid, int r, int c) {
      cout << "find_maze_path ["<<r<<"]["<<c<<"]"<<endl;
      // testing only
      /*
      cout<<""
      for(int row = 0; row < r; row++) {
	        for(int col = 0; col < c; col++) {
	            cout << grid[row][col];
	        }
	        cout << endl;
	    }
	    */
      if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size())
        {return 0;  }    // Cell is out of bounds. 
      else if (grid[r][c] != PATH && grid[r][c]!= '@' && grid[r][c]!='$')
        {return 0;   } // cannot move to wall or previously moved areas.
      else if (r == grid.size()  - 1 && c == grid[0].size() - 1) {
         grid[r][c]= MOVE;
        return 1;               // maze exit.
      }
      else { 
        // Recursively find path from neighbor
         grid[r][c]= MOVE;
        int found = (find_maze_path(grid, r - 1, c) + find_maze_path(grid, r + 1, c) +find_maze_path(grid, r, c - 1) + find_maze_path(grid, r, c + 1 ) );
        if (found >0){
            return found;
        }
        else{
            grid[r][c] = TEMPORARY;  // Dead end.
            return 0;
        }
      }
    }
int main(){
  int x, y;
  cin>>x>>y;
  
  vector<vector<char>> maze_grid;
  for (int i=0;i<x; i++){
          vector<char> x1; 
      for (int j=0;j<y; j++){
          char temp;
          cin>>temp;
          x1.push_back(temp);
      }
          maze_grid.push_back(x1);
  }
  
  /*
    for (int i = 0; i < maze_grid.size(); i++) { 
        for (int j = 0; j < maze_grid[i].size(); j++) 
            cout << maze_grid[i][j]; 
        cout <<" "<< endl; 
    } 
    */
  int sol = find_maze_path(maze_grid, 0,0);
  cout<<sol;
  return 0;
}

sample input:
16 18
@ + + + + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + + + + +
+ + + + + + + + + + X + + X + + + X
+ + + + + + + + + X X + + + + + + X
+ + X + + + + + + + + X X + + + + +
+ + + + + + + + + + + + + + X + + +
+ + + + + X + + X + + + + + + X + +
+ + + + + + + + + + + + + + + + + +
+ + + + + + X + + + + + + + + X + +
+ + + + + + + + + + + + + + + + + +
+ + + X + + + + + + + X + + + + X +
+ X X + + X + + + + + + + + + + X +
+ + + + + + + + + + + + + + + + + +
+ X + + + + + X + + + + + + + + X +
+ + X + + + + X + + + X + + + X + +
+ X X + + X + + + + + + + + + X + $

how do I improve this algorithm?

[salem c]

> int find_maze_path(vector<vector<char>> grid, int r, int c)
Every recursive call is going to get a completely fresh copy of the grid.

So changes you make which outer layers rely on won't see what you did.

At a guess.
int find_maze_path(vector<vector<char>> &grid, int r, int c)



> sample input:
> 16 18
Start with the smallest grid that isn't completely trivial, say 3x3 and then use the debugger to step through the code.

[lastchance]

You are trying ALL paths (line 36). If you are OK then continue on that path only, without trying the others.

You are also entitled to stop when you get to the end point, not continue trying everything else.

[GonlyG]

I have to output the amount of paths you can take to the exit.

edit: I just realized the problem said you can only move right or down, making the program much simpler. But the program is still getting runtime exceed even with only checking r+1 and c+1.

[lastchance]

If you can only move right or down then simply work along the successive / diagonals, filling in the number of paths to get to that point.

You DON'T need a recursive algorithm for that: it's a completely different problem to your original.

[jonnin]

this is the kind of problem where you can exploit knowledge for speed using an algorithm that won't work for all maze problems but will solve yours.

1) what are all the possible paths if there are no obstacles?
2) which paths are destroyed by an obstacle (all the paths that contain that square)
3) result is what was left.

the key to the above is finding all the possible paths in #1 efficiently. given that you have 2 choices at each square, you can generate them fairly easily: its basically a form of binary where 1 can be right and 0 down or whatever. You also know the sizes ... the longest path is all the way down then all the way over, and the shortest path is the diagonal (but you can't move diagonally, so where does that leave you?)

what I am telling you is that you can actually generate the result without traversing the maze at all.

[GonlyG]

Thanks for the tip, though... I'm also solving an extension of the problem where you can go up, down, left, right and (probably) have to traverse to find three ways to the maze, from the top right, bottom right, and bottom left. The solution is timing out after finding one way. How do I improve the algorithm?

[salem c]

I guess the thing to do is to read the question again, and as jonnin says, figure out what the essence of the problem is and solve it.

> I borrowed a recursive maze path finder algorithm
Not google for the first maze solving code you can find, then wonder why it doesn't perform adequately.

But if you want more than "pin the tail on the donkey" guesses as to what is wrong, you should post your actual question - all of it.
Not some paraphrased interpretation and broken code attempting to answer it.

[oneidacharisse]

Because there, someone feels like he's helping ??? lol Where some people came to reassure themselves about their little power they acquired on the forum ??? Sometimes some people are scary, how do you learn with this kind of behavior?

There's a topic with a proposed solution to try to understand how to do it GonlyG :

http://www.cplusplus.com/forum/general/127314/
http://www.cplusplus.com/forum/general/76838/

Good luck with that.