递归查找网格中的所有路径

Question

我正在编写一个小程序，在给定一些需要避开的墙壁的情况下，递归地计算网格上到 (0,0) 的所有路径。网格看起来像这样：

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

您必须在路径中不增加到原点的距离的情况下到达原点。

我写了这段代码来查找所有路径：

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);
}

注意：GRID_TRAVLLED 和 GRID_BLOCKED 是在程序其他地方定义的值，但本质上只是表示有墙或点的标记已经旅行了。

然而，当运行时，程序输出零路径！不可否认，我不确定有多少条路径，但我至少可以数出一些，因此它不能为零。

有人知道这里出了什么问题吗？

提前致谢

编辑

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

使用这个网格，我得到了一个无限循环.... 更新代码：

  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);
}

让它静置一段时间后 return 540。我几乎可以肯定在这种情况下不可能有 540 条路径

Answer 1

我注意到：

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);

(x + 1, y) 和 (x - 1, y) 这两个点不能都更接近原点，但是你将 (distance - 1) 传递给这两个递归调用。这将导致许多路径的距离最终等于 -1，然后将 return 0，但在它们 return 0 之前，这些路径将被标记为已走过，尽管这些路径是应该被阻止的虚假路径正在旅行。

您应该只检查靠近原点的路径，即 (x -1, y) 和 (x, y - 1)

递归查找网格中的所有路径

Recursively finding all paths in a grid

c++

grid

recursion

vector

2d-vector