3D迷宮遞歸方法 - C++

Question

我在C使3D迷宮++。我在遞歸方法中找到兩個端點（起點爲m [0] [0] [0];端點爲m [7] [7] [7];））之間的有效路徑時遇到了問題。它檢查陣列中的位置。如果它的內容是1，那麼它是路徑的有效部分;如果爲0，則不是路徑的有效部分。這裏是我的方法：

bool Maze::findPath(int row, int column, int level,string path){ 
cout << "findPath " << row << ", " << column << ", " << level << " value " << m[row][column][level] << endl; 
if(row < 0 || row > 7 || column < 0 || column > 7 || level < 0 || level > 7){ 
    cout << "Out of bounds" << endl; 
    //system("PAUSE"); 
    return false; 
} 
else if(m[row][column][level] == 0){ 
    cout << "spot is zero" << endl; 
    //system("PAUSE"); 
    return false; 
} 
else if(visited[row][column][level] == 1){ 
    cout << "visited" << endl; 
    return false; 
} 
else if(row == 7 && column == 7 && level == 7 && m[row][column][level] == 1){ 
    cout << "Found!" << endl; 
    //system("PAUSE"); 
    return true; 
} 
else{ 
    visited[row][column][level] = 1; 
    //cout << "searching..." << endl; 
    if(row < 7 && findPath(row + 1,column,level,path)) 
     return true; 
    if(column < 7 && findPath(row,column + 1,level,path)) 
     return true; 
    if(level < 7 && findPath(row,column,level + 1,path)) 
     return true; 
    if(row > 7 && findPath(row - 1,column,level,path)) 
     return true; 
    if(column > 7 && findPath(row,column - 1,level,path)) 
     return true; 
    if(level > 7 && findPath(row,column,level - 1,path)) 
     return true; 
} 
return false; 

}

所以對於方法檢查「出界」，路徑（零），拜訪位置上的無效點。我不確定我錯過了什麼，但是這個方法返回到不可解的迷宮。有人可以看到我的遞歸調用可能會遺漏一些明顯的錯誤嗎？由於

編輯：修正了一些代碼錯誤，但它似乎仍然是「解決」無法解決的迷宮。

下面是跟它可解迷宮的例子是不可能解決：

1 0 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 1 
0 0 0 1 0 0 0 0 
1 0 0 1 0 1 0 0 
0 0 0 1 0 0 0 0 
1 0 0 1 0 0 0 1 

1 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 
1 1 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 
0 1 1 0 0 0 0 0 
0 0 0 1 0 1 1 1 

0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 1 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 1 0 0 0 0 

0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
1 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 

1 1 1 1 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 1 0 0 0 1 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 1 0 
1 0 0 0 0 1 0 0 
0 1 0 0 0 0 0 0 
1 0 0 0 0 0 0 1 

1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 1 0 
1 1 1 1 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 1 0 0 0 0 
1 1 1 1 0 0 0 1 

1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 1 0 0 0 0 0 

0 0 1 0 0 0 0 1 
0 0 1 0 0 0 0 1 
0 0 1 0 0 0 0 1 
0 0 1 0 0 0 0 1 
0 0 1 1 0 0 0 1 
0 0 0 1 0 0 0 1 
0 0 0 1 0 0 0 1 
0 0 0 1 1 1 0 1 

Answer 1

有一個在findPath(++row,column,level,path)（以及類似的遞歸調用）一個問題：你不想要的變量增量繼續進行其他遞歸調用。 （例如，findPath(row,++column,level,path)中的變量row會受到第一次遞歸調用的影響。）

改爲使用findPath(row + 1,column,level,path)（以及類似的）。

而且，在過去三次遞歸調用，你沒有做出正確的測試：

//instead of level < 7 
if(level < 7 && findPath(--row,column,level,path)) //should be row > 0 
    return true; 
if(level < 7 && findPath(row,--column,level,path)) //should be column > 0 
    return true; 
if(level < 7 && findPath(row,column,--level,path)) //should be level > 0 
    return true; 

編輯

但是，你實際上並沒有因爲你過濾掉out of bounds錯誤需要這些測試在遞歸函數的頂部。因此，這些呼叫可以被簡化爲：

return findPath(row + 1,column,level,path) || findPath(row,column + 1,level,path) 
      || findPath(row,column,level + 1,path) || findPath(row - 1,column,level,path) 
      || findPath(row,column - 1,level,path) || findPath(row,column,level - 1,path); 

此外，測試&& m[row][column][level] == 1是多餘的，因爲在取else if(m[row][column][level] == 0)的照顧。 （順便提一下，在我第一次調用這個函數之前，我會檢查m[7][7][7]）。

Answer 2

我剛完成這個算法作爲一個類的賦值，我們只使用了一個5x5塊作爲迷宮，但是我發現每次從任何角度到達塊時，它都會非常緩慢地測試所有可能性，我發現通過將數組中的值設置爲0，可以顯着提高程序的速度，因爲您確定它們無用。我在函數結尾的return false處做過。