c++ - Word Solver - 所有方向

Question

我为所有方向创建了一个单词求解器。它可以水平、垂直和反向查找单词。然而，我在让它走向各个方向时遇到了问题。所以把“你好”放在:

H  E  i  l
x  L  p  q
c  L  O  m

任何人都可以指出我该怎么做？这是我搜索单词的算法(在 C++ 中):

/*
 * For loops that search each row, each column in all 8 possible directions.
 */
void Scramble::solve() {

cout << "Output:" << endl;

for (int row = 0; row < getRows(); row++) {
    for (int col = 0; col < getCols(); col++)
        for (int rowDir = -1; rowDir <= 1; rowDir++)
            for (int colDir = -1; colDir <=1; colDir++)
                if (rowDir != 0 || colDir != 0)
                    findWords(row, col, rowDir, colDir);
}
}

/*
 * Finds the matches in a given direction. Also calls verifyWord() to verify that the
 * current sequence of letters could possibly form a word. If not, search stops.
 */
void Scramble::findWords(int startingRow, int startingCol, int rowDir, int colDir) {

int searchResult;
string sequence = "";
sequence = sequence + wordsArr[startingRow][startingCol];

for (int i = startingRow + rowDir, j = startingCol + colDir; i >= 0 && j >= 0
&& i < getRows() && j < getCols(); i = i + rowDir, j = j + colDir) {

    sequence = sequence + wordsArr[i][j];

    if (sequence.length() >= 3) {

        searchResult = verifyWord(words, sequence);

        if ((unsigned int)searchResult == words.size())
            break;

        if (words[searchResult].rfind(sequence) > words[searchResult].length())
            break;

        if (words[searchResult] == (sequence))
            cout << sequence << endl;
    }
}
}

/*
 * Performs the verifyWord search method.
 * Searches the word to make sure that so far, there is possibly that the current sequence
 * of letter could form a word. That is to avoid continuing to search for a word
 * when the first sequence of characters do not construct a valid word in the dictionary.
 *
 * For example, if we have 'xzt', when this search is done it prevents the search
 * to continue since no word in the dictionary starts with 'xzt'
 */
int Scramble::verifyWord(vector<string> words, string str) {

int low = 0;
int mid = 0;
int high = words.size();

while (low < high) {

    mid = (low + high) / 2;

    if (str > words[mid]) {
        low = mid + 1;
    }

    else if (str < words[mid]) {
        high = mid - 1;
    }

    else
        return mid;
}
}

Answer 1

这里有一个有趣的思考方式:找到单词类似于走迷宫。 “开始”和“结束”对应于您要查找的单词的开头和结尾，“死胡同”对应于路径与单词之间的不匹配，“成功”是指路径中的字符串是一场比赛。

这里的好消息是有很多关于迷宫解决算法的资源。我熟悉并且不太难实现的一种特定算法是 recursion with backtracking .

显然，为了解决您的问题，必须进行一些更改。例如，您不知道起点在哪里，但幸运的是这无关紧要。您可以检查每一个可能的起始位置，并且由于不匹配，其中许多无论如何都会在第一步中被丢弃。