我正在寫一個小程序,在給定一些需要避免的墻的情況下,calculates--recursively--all路徑到網格上的(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是程序中其他地方定義的值,但本質上只是表示有一堵墻或該點已在上面移動的標記。
然而,當運行時,程序輸出有零路徑!誠然,我不確定有多少條路徑,但我至少可以數一數,所以它不可能是零。
有人知道這里出了什么問題嗎?
提前謝謝
edit
. . . . . . . . . . . . . . . . . . .
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條路徑
我注意到:
兩個點(x+1,y)和(x-1,y)不能都離原點更近,但是你要把(距離-1)傳遞給這兩個遞歸調用。這將導致許多路徑的距離最終等于-1,然后返回0,但在返回0之前,這些路徑將被標記為已行駛,盡管它們是本應防止行駛的虛假路徑。
應該只檢查靠近原點的路徑,即(x-1,y)和(x,y-1)