C++使用遞歸進行騎士之旅

我創建了一個專門爲此目的處理2D矢量的類板。我正在努力解決騎士之旅。我想在完成時打印出來。使用遞歸voyagingKnight（）函數，我發現它不做任何事情，不打印結果。看來，我想增加遞歸調用的步數，但這是行不通的。C++使用遞歸進行騎士之旅

矢量自變量incs是用於移動騎士的增量矢量的第2個矢量，每行中第一列移動一行，第二列移動列移動。

有沒有人有任何建議，我在這裏的推理缺陷？相關的代碼

bool voyaging_knight(Board &board, int i, int j, int steps ,vector< vector<int> > &increments) 
    { 
     if(!newplace(theboard, i, j)) return false; 
     board.setval(i,j,step); 

     if(gone_everywhere(board, steps)) 
     { 
     cout <<"DONE" << endl; 
     board.showgrid(); 
     return true; 
     } 

     int n; 
     int in, jn; 
     for(n=0; n<8; n++) 
     { 
      in = i + increments[n][0]; 
      jn = j + increments[n][1]; 

      if(inboard(board, i, j)&& newplace(board,i,j)) 
      { 

      voyaging_knight(board, in, jn, steps+1 ,increments); 

      return true; 
      } 
     } 


     theboard.setval(i,j,-1); 

    }

來源

2014-03-05 user37460

這將是一個正常的棋盤上64個電話非常深的遞歸。你確定你不想只使用循環？ – lapk

是的，改變這種：

voyagingKnight(theboard, inext, jnext, step+1 ,incs); 
return true;

要這樣：

return voyagingKnight(theboard, inext, jnext, step+1 ,incs);

此外，看來你需要在返回的東西（可能false）函數結束。

順便說一下，我假設你已經將theboard中的所有條目初始化爲-1。

來源

2014-03-05 09:01:43

我猜你想要一個連續的路徑由一個（回合）棋盤上的馬運動所發現的回溯。在這種情況下，你必須通過價值傳遞董事會，所以你採取的每條路徑都有自己的實例來填充。通過參考傳遞，每條路徑都會填充同一塊電路板，因此您無法採取所有步驟。

此外，您應該通過值傳遞一個結果並填充它所訪問的位置並從遞歸函數返回它，因此每個路徑都有它自己的結果位置實例，並通過返回它，最終得到最終結果。

您不應該通過inc，因爲這只是一個不會更改的輔助容器。

來源

2014-03-05 09:13:55 stefaanv

我更新了我的答案，因爲我誤解了傳遞的公式作爲結果。在達到最後位置時顯示結果（完成完成的棋盤），但對於回溯，理想情況下，將返回遞歸函數的結果。 – stefaanv

使板子成爲一個全局變量，並在全局變量中建立一系列訪問過的正方形。確保在撤消每個暫定步驟時撤銷任何更改（方形訪問，序列的最後一步）。打電話給騎士的導遊功能，如果到達最後就返回成功，並在完成後做任何輸出。

將整個shebang包裝在一個文件或一個類中，以便不泄露私人細節以窺探。

來源

2014-03-08 16:35:36 vonbrand

C++使用遞歸進行騎士之旅

回答

相關問題