我意识到这段代码可能读起来有点密集,我试图做的是将标准的递归迷宫求解算法(在尝试找到所有解决方案之前尝试所有方向)改编为“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;
}

最佳答案

不确定这是否是唯一的问题,但是currentWord += ...仅应为currentWord + ....探测到4个方向中的每个方向时,+=都会更改本地currentWord变量,而不是简单地将新的currentWord传递给递归函数。

08-25 08:11