如果可能，使用递归查找网格中的路径

Question

给定一个网格，大小为R X C，网格中的人的startPosition和endPosition由零和一组成。现在我想找到从开始位置到结束位置的路径，并且通过标记它们来追踪网格上标记的路径2.如果路径不可能，我需要告诉路径是不可能的。所以我写了这个逻辑：

vector<vector<int>> solution; 
void printSolution(vector<vector<int>> grid) 
{ 
for (int i=0;i<grid.size();i++) 
{ 
    for (int j=0;j<grid[i].size();j++) 
     cout<<grid[i][j]<<" "; 
    cout<<endl; 
} 
} 

bool isSafe(vector<vector<int>> grid, pair<int,int> position) 
{ 
if(position.first >= 0 && position.first < grid.size() && 
    position.second >= 0 && position.second < grid[0].size() && 
    grid[position.first][position.second] == 0) 
    return true; 

return false; 
} 

bool checkPath(vector<vector<int>> grid,pair<int,int> currentPosition,pair<int,int> endPosition){ 
if(currentPosition == endPosition) 
{ 
    solution[currentPosition.first][currentPosition.second] = 2; 
    return true; 
} 
if(isSafe(grid,currentPosition) == true) 
{ 
    solution[currentPosition.first][currentPosition.second] = 2; 
    if (checkPath(grid, make_pair(currentPosition.first+1,currentPosition.second),endPosition) == true) 
     return true; 
    if (checkPath(grid, make_pair(currentPosition.first-1,currentPosition.second),endPosition) == true) 
     return true; 
    if (checkPath(grid, make_pair(currentPosition.first,currentPosition.second+1),endPosition) == true) 
     return true; 
    if (checkPath(grid, make_pair(currentPosition.first,currentPosition.second-1),endPosition) == true) 
     return true; 
    solution[currentPosition.first][currentPosition.second] = 0; 
    return false; 
} 

return false; 
} 

bool solver(vector<vector<int>> grid,pair<int,int> startPosition,pair<int,int> endPosition,int R,int C){ 
solution.resize(R,vector<int>(C)); 
bool isPath = checkPath(grid,startPosition,endPosition); 
printSolution(solution); 
if(isPath==false){ 
    cout<<"No Path Found"<<endl; 
    return false; 
} 
else{ 
    cout<<"Path Found"<<endl; 
    return true; 
} 
} 

此代码给出了分段错误。请帮助找到它。我坚持了将近一整天，以找到它的存在。

所以帮助我纠正代码的逻辑。假设我有以下字段：

int R,C; 
int grid[R][C]; 
pair<int,int> startPosition; 
pair<int,int> endPosition; 

此递归运行无限。我检查对于简单的情况下与指定startPosition为（1,0）和终端位置为（2,2），R = 3，C = 3和网格为：

1 1 1 
0 0 1 
1 0 0 

首先，我试图与BFS，然后开始做出递归解决方案。

Answer 1

实施BFS路径查找算法时，它有助于创建一个影子阵列，用于跟踪所有访问节点与原点之间的距离。

int distance[R][C]; 

最初，将所有距离设置为-1表示该位置尚未被访问。然后将原点的距离设置为0，然后将原点推入堆栈。

堆栈不空时，从堆栈中弹出一个项目。对于每个相邻位置（尚未访问过的位置），设置该位置的距离，并推送该位置。

当您到达结束位置时，您可以通过反向工作找到路径。知道结束位置处的距离，路径上的前一个点是已经访问的相邻位置，并且具有较低的距离。