Traveral迷宮和深度優先搜索

今天我已經學習了DFS，今天我嘗試了練習。Traveral迷宮和深度優先搜索

我在我的程序中遇到問題。

void dfs(int x,int y){ 
    if(maze[x][y]==0) maze[x][y]=2; 
    if(maze[8][8]==2){ 
    flag=true; 
    return; 
    } 
    if(maze[x+1][y]==0 && x+1<9){ 
    maze[x][y]=2; 
    maze[x+1][y]=2; 
    dfs(x+1,y); 
    if(f lag==false){ 
     maze[x+1][y]=0; 
     maze[x][y]=0; 
    } 
    } 
    else if(maze[x][y+1]==0 && y+1<9){ 
    maze[x][y]=2; 
    maze[x][y+1]=2; 
    dfs(x,y+1);         
    if(flag==false){ 
     maze[x][y+1]=0; 
     maze[x][y]=0; 
    } 
    } 
    else if(maze[x-1][y]==0 && x-1>0){ 
    maze[x][y]=2; 
    maze[x-1][y]=2; 
    dfs(x-1,y);         
    if(flag==false){ 
     maze[x-1][y]=0; 
     maze[x][y]=0; 
    } 
    } 
    else if(maze[x][y-1]==0 && y-1>0){ 
    maze[x][y]=2; 
    maze[x][y-1]=2; 
    dfs(x,y-1);         
    if(flag==false){ 
     maze[x][y-1]=0; 
     maze[x][y]=0; 
    } 
    } 
    return; 
}

1. 的鏈接是我寫的程序，但我不知道如何找到最短路徑。

2. 你可以給我一些關於如何使用堆棧的建議，我只使用遞歸。我已經看到了關於它的wiki，但是仍然不能理解如何使用堆棧（例如，如何使用1 -D陣列記錄約2-d陣列的地步，我對此很困惑）

感謝您花時間閱讀我的問題

來源

2012-03-09 Liang-Yu Pan

請將相關代碼發佈到您的問題中，並確保您的縮進不會像在鍵盤 – 111111 2012-03-09 18:00:26

中那樣。另外，如果你不喜歡深刻的縮進，我建議你避免內核代碼。 – Alex 2012-03-09 18:07:59

@ 111111：請不要粗暴（至少看似）初學者。當我開始編程時，我根本沒有縮進，而且離這裏還有很長的路要走。我們都是初學者一次。 – LiKao 2012-03-09 18:10:22

有多個點，在這種情況下發表評論：

1）最簡單的堆棧是遞歸堆棧，您似乎已經在使用您的代碼。即無論何時從函數dfs()本身調用dfs()，所有變量都將被放入堆棧。在你的情況下，當你調用x和y將被保存以便稍後返回。即一旦你從dfs() x回來，y將具有與你打電話前相同的價值。

2）在返回之前，您必須撤消上次更改。在你的功能開始時，你設置了maze[x][y]=2。在你回來之前，你必須撤銷這個，因爲這個空間可能導致死衚衕。

3）DFS可用於查找任何內存使用率較低的路徑。但是，DFS找到的路徑可能不是最短的路徑。還有另一種稱爲BFS的算法，它可以找到最短路徑，但是具有更高的內存使用率。然後是迭代DFS，它將找到最短路徑，具有低內存消耗，但需要更多時間。你必須決定你想要的，然後選擇你的算法。

來源

2012-03-09 18:08:53 LiKao

Thx爲您提供幫助！ – 2012-03-09 18:32:09

找到最短路徑的BFS比DFS更好。

您可以使用2個1維數組來表示2-D迷宮中的一個點。

我曾經有xq [maxlength]，yq [maxlength]作爲遍歷2D迷宮的隊列。

當你要插入一個新的位置（XI，YI）到隊列做

xq[back] = xi; 
yq[back] = yi; 
back++;

，當你想從一個隊列點（XP，YP），

xp = xq[front]; 
yp = yq[front]; 
front++;

最初有前面和後面是0.隊列完成了，你可以用它做一個BFS。

來源

2012-03-09 18:09:20

Thx爲您提供幫助！ – 2012-03-09 18:32:15

Traveral迷宮和深度優先搜索

回答

相關問題