如果可能，使用遞歸查找網格中的路徑

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，然後將原點推入堆棧。

堆棧不空時，從堆棧中彈出一個項目。對於每個相鄰位置（尚未訪問過的位置），設置該位置的距離，並推送該位置。

當您到達結束位置時，您可以通過反向工作找到路徑。知道結束位置處的距離，路徑上的前一個點是已經訪問的相鄰位置，並且具有較低的距離。