Recursively finding all paths in a grid-CodePudding

I am writing a small program that calculates--recursively--all paths to (0,0) on the grid given some walls that need to be avoided. The grid looks something like this:

 . . . . . . . . . . .
 | . . | . . . . . . .
 . . | . . . . . . . .
 . . - - - . . - - - -
 . | . . . . . | . . .
 . . . . . | . | . . .
 . . . . . . - - . . .
 . - - - . . . | . . .
 . | . . . . . | . . .
 . | . . . . . . . . .
 . . . | . . . . . . O

You must get to the origin without ever increasing distance to the origin in your path.

I have written this code to find all paths:

int recursive_find_path(unsigned int x, unsigned int y, unsigned int distance, std::vector<std::vector<GRID_STATUS> > blocked_grid){
  //if(x>blocked_grid.size()-1 or y>blocked_grid[x].size()-1 or x<0 or y<0 or x y > distance or blocked_grid[y][x] == GRID_BLOCKED or blocked_grid[y][x] == GRID_TRAVELLED)
  if(x>blocked_grid.size()-1 or y>blocked_grid[x].size()-1 or x<0 or y<0 or x y<distance or blocked_grid[y][x] == GRID_BLOCKED){
    return 0;
  }
  if(blocked_grid[y][x] == GRID_TRAVELLED){
    return 0;
  }
  if(x==0 and y==0){
    return 1;
  }
  blocked_grid[y][x] = GRID_TRAVELLED; // set position to 'travelled' on to avoid infinite recursion
  return recursive_find_path(x-1,y, distance-1,blocked_grid) recursive_find_path(x,y-1, distance-1, blocked_grid) recursive_find_path(x 1,y, distance-1, blocked_grid);
}

NOTE: GRID_TRAVLLED and GRID_BLOCKED are values defined elsewhere in the program but essentially are just tokens to indicate that there is a wall or the point has been travelled on.

However, when running, the program outputs that there are zero paths! Admittedly, I am not sure how many paths there are but I can at least count a few thus it can't be zero.

Does anyone know what is going wrong here?

Thanks in advance

edit

 . . . . . . . . . . . . . . . . . . .
 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
 . . . . . . . X . . . . . . . . . . .
 . . . . . . . X . . . . . . . . . . .
 . . . . . . . X . . . . . . . . . X S

Using this grid, I get an infinite loop.... updated code:

  if(x>blocked_grid.size()-1 or y>blocked_grid[x].size()-1 or x<0 or y<0 or blocked_grid[y][x] == GRID_BLOCKED){
    return 0;
  }
  if(x==0 and y==0){
    return 1;
  }
  return recursive_find_path(x-1,y,blocked_grid) recursive_find_path(x,y-1, blocked_grid);
}

after letting it sit for a while it did return 540. I am almost certain there can't be 540 paths in this case

CodePudding user response：

I noticed at:

return recursive_find_path(x-1,y, distance-1,blocked_grid) recursive_find_path(x,y-1, distance-1, blocked_grid) recursive_find_path(x 1,y, distance-1, blocked_grid);

The two points (x 1, y) and (x - 1, y) cannot both be closer to the origin, yet you pass (distance - 1) to both of those recursive calls. This will cause distance to eventually equal -1 for many paths, which will then return 0, but until they return 0, those paths will be marked as travelled despite being spurious paths that should have been prevented from being travelled.

You should only check paths that move closer to the origin, those being (x -1, y) and (x, y - 1)