我正在撰寫一個小程式，在給定一些需要避免的墻壁的情況下，遞回地計算網格上所有到 (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);
}
讓它靜置一段時間后，它確實回傳了 540。我幾乎可以肯定在這種情況下不可能有 540 條路徑
uj5u.com熱心網友回復：
我注意到：
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，然后回傳 0，但在它們回傳 0 之前，這些路徑將被標記為已通過，盡管這些路徑是本應阻止行駛的虛假路徑。
您應該只檢查靠近原點的路徑，即 (x -1, y) 和 (x, y - 1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/435108.html
上一篇：計算e^x時出現運行時錯誤
下一篇：在javascript中使用filter()來實作curriable()是可行的，但是，uisngmap()是可行的，為什么？