パストレースを使用した最初の検索で、一部の座標が「スキップ」されました

Question

私は、終点から始点までのパスをトレースする機能が追加されたグリッドに幅優先検索の実装を作成しています。私はパスをトレースすることに問題がありますが、Breadth First Searchアルゴリズムは期待どおりに機能しました。それはどういうわけか特定の座標を "スキップ"しました。

は、このサンプル入力を考えてみましょう：

Shortest Distance to the End Point: 4 
Shortest Path Route: 
X|X 
XXX 
... 

しかし、その代わりに私のプログラムは私を与える：

3 3 //Grid Dimension (Row Column) 
S|E //'S' = Start Point, 'E' = End Point 
... //'.' = Empty Space, '|' = Wall 
... 

は、私は、出力は次のようになり期待

Shortest Distance to the End Point: 4 
Shortest Path Route: 
S|X 
XX. 
... 

私は位置を確認しましたし、起源は正しい。まず、BFSアルゴリズムの中で、各点の原点を印刷しました。次に、パストレースアルゴリズムでは、現在の座標と、その点の原点を表示しました。ここで私はプリントアウト何：

//First debug: Inside BFS 
The origin for (1, 0) is (0, 0) 
The origin for (1, 1) is (1, 0) 
The origin for (2, 0) is (1, 0) 
The origin for (1, 2) is (1, 1) 
The origin for (2, 1) is (1, 1) 
The origin for (0, 2) is (1, 2) 
The origin for (2, 2) is (1, 2) 

//Second Debug: Inside Path Trace 
From (0, 2) going to the origin, which is (1, 2) 
From (1, 1) going to the origin, which is (1, 0) 
From (1, 0) going to the origin, which is (0, 0) 

事が(1, 2)がトレースパスにスキップしてしまった、あります。しかし、それは(1, 1)である(1, 2)の起点を次の点として認識しました。

私はので、ここでパストレース機能です、（少なくともBFSそれは正しく動作中）私のコードで間違った何も表示されませんので、私のコード：この1の

//On every point, I initially set the origin to be (-1, -1) 
//Through the BFS, each point set its own origin 
//If it is certain that there's a path from the Start Point to the End Point, 
//Then from the End Point, I can traverse the origin until I reach (-1, -1) 

coordinate currentPoint = endPoint; 
while ((currentPoint.row != -1) && (currentPoint.col != -1)) { 
     map[currentPoint.row][currentPoint.col] = 'X'; 
     currentPoint.row = mapData[currentPoint.row][currentPoint.col].origin.row; 
     currentPoint.col = mapData[currentPoint.row][currentPoint.col].origin.col; 
} 

任意の洞察力？これらの行に感謝

Answer 1

：

currentPoint.row = mapData[currentPoint.row][currentPoint.col].origin.row; 
    currentPoint.col = mapData[currentPoint.row][currentPoint.col].origin.col; 

あなたはその後、2行目にそれを使用して、最初の行にcurrentPoint.rowの値を変更しています。

int newRow = mapData[currentPoint.row][currentPoint.col].origin.row; 
    int newCol = mapData[currentPoint.row][currentPoint.col].origin.col; 
    mapData[currentPoint.row][currentPoint.col].origin.row = newRow; 
    mapData[currentPoint.row][currentPoint.col].origin.col = newCol 

はそれを修正します：これは、あなたの代わりに（0,2）のような

何かを（1,2）のCOLを取得していることを意味します。