C++ : 재귀 backtracking boggle grid

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 + ....+=은 4 각으로 지역 currentWord 변수를 변화해야하지 새로운 currentWord을 단순히 재귀 함수로 전달하기보다는 방향을 조사합니다.