C++：遞歸回溯驚奇電網

Question

我意識到這個代碼可能會有點密密麻麻地寫着什麼從來就試圖做的是適應標準的遞歸迷宮解決算法 - 所有方向嘗試，直到找到一個解，到遊戲'boggle'的算法，該算法檢查目標單詞是否可以通過沿四個方向中的任一方向在網格上形成。我意識到這段代碼有一個以上的錯誤，但我很想知道如何解決最重要的問題，例如搜索網格的方向和方式顯然不起作用。

控制檯輸出：

Enter word: 
aefn 
First matching letter found at [row: 0] [col: 0] 
findNext: Point location: Y[0] X[0] 

Point location: Y[0] X[-1] 
A //(This is the algorithm trying to find "targetWord" on grid "currentWord") 
Point location: Y[1] X[0] 
AA 
Point location: Y[0] X[0] 
AAE 
Point location: Y[0] X[-1] 
AAEA 
Point location: Y[1] X[0] 
AAEAA 
Point location: Y[0] X[1] 
AAEAAA 
Point location: Y[-1] X[0] 
AAEAAAA 
Point location: Y[1] X[1] 
AAEE 
Point location: Y[1] X[0] 
AAEEU 
Point location: Y[2] X[1] 
AAEEUU 
Point location: Y[1] X[2] 
AAEEUUU 
Point location: Y[0] X[1] 
AAEEUUUU 
Point location: Y[0] X[2] 
AAEEE 
Point location: Y[-1] X[1] 
AAEEEE 
Point location: Y[0] X[1] 
AAA 
Point location: Y[1] X[-1] 
AAAE 
Point location: Y[2] X[0] 
AAAEE 
Point location: Y[1] X[1] 
AAAEEE 
Point location: Y[0] X[0] 
AAAEEEE 
Point location: Y[-1] X[0] 
AAAA 

代碼：

enum Direction { NORTH, 
       EAST, 
       SOUTH, 
       WEST }; 






/** Attempts to find a matching letter on the grid to the first letter in the 
    * targetWord, if found it stores it location in grid in 'point' and calls 
    * findNext() with the location of matching letter stored in the 'point'. 
    */ 
bool findMatchingFirstLetter(Grid<char> &cubeGrid, string currentWord, string targetWord, int index) 
{ 

    for (int row = 0; row < cubeGrid.numRows(); row++) 
    { 
     for (int col = 0; col < cubeGrid.numCols(); col++) 
     { 
      if (cubeGrid.get(row, col) == targetWord[0]) 
      { 
       cout << "First matching letter found at [row: " << row << "] [col: " << col << "]" << endl; 
       GPoint point(col, row); 
       cout << "findNext: " << findNextRecur(cubeGrid, currentWord, targetWord, index, point) << endl; 

      } 
     } 
    } 
    return false; 
} 



/** Recursive function. 
    * Exhaustively searches the grid for all possible combinations, moving in all 
    * compass directions. */ 
bool findNextRecur(Grid<char> &cubeGrid, string currentWord, string targetWord, int index, GPoint point) 
{ 
    cout << "Point location: Y[" << point.getY() << "] X[" << point.getX() << "]" << endl; 
    cout << currentWord << endl; 
    if (currentWord == targetWord) 
     return true; 
    if (currentWord.length() > targetWord.length() || 
     point.getX() > cubeGrid.numCols() || 
     point.getX() < 0 || 
     point.getY() > cubeGrid.numRows() || 
     point.getY() < 0) 
    { return false; } 


    for (Direction dir = NORTH; dir <= WEST; dir++) 
    { 

     if (findNextRecur(cubeGrid, 
          currentWord += cubeGrid.get(point.getY(), point.getX()), 
          targetWord, 
          index, //index is currently not in use. 
          adjacentPoint(point, dir))) 
     { return true; } 
    } 
} 



GPoint adjacentPoint(GPoint point, Direction dir) 
{ 
    switch (dir) { 
     case NORTH: return GPoint(point.getY()-1, point.getX()); 
     case EAST: return GPoint(point.getY(), point.getX()+1); 
     case SOUTH: return GPoint(point.getY()+1, point.getX()); 
     case WEST: return GPoint(point.getY(), point.getX()-1); 
    } 
    return point; 
} 


/** Wrapper 
    */ 
bool findWordOnGrid(Grid<char> &cubeGrid, string word) 
{ 
    cout << findMatchingFirstLetter(cubeGrid, "", toUpperCase(word), 0) << endl; 
    return true; 
} 

Answer 1

不知道這是否是唯一的問題，但currentWord += ...只應currentWord + ....的+=正在改變當地currentWord變量中的4方向被探測，而不是簡單地將新的currentWord傳遞給遞歸函數。