C++ Boggle 代码

以下是一个简单的 C++ 实现，使用了递归和回溯法来解决 Boggle 游戏问题。该算法基于深度优先搜索和字典树（Trie）结构。

#include <bits/stdc++.h>
using namespace std;

#define M 3
#define N 3
#define MAX_WORD_LEN 10

// Trie 节点
struct TrieNode {
    bool endOfWord; // 是否是单词的结尾
    TrieNode* children[26]; // 每个节点最多有 26 个子节点
};

// 创建一个新的 Trie 节点
TrieNode* getTrieNode() {
    TrieNode* node = new TrieNode;
    node->endOfWord = false;
    for (int i = 0; i < 26; i++) {
        node->children[i] = nullptr;
    }
    return node;
}

// 将单词插入到 Trie 中
void insert(TrieNode* root, string word) {
    TrieNode* curr = root;
    for (int i = 0; i < word.length(); i++) {
        int index = word[i] - 'a';
        if (curr->children[index] == nullptr) {
            curr->children[index] = getTrieNode();
        }
        curr = curr->children[index];
    }
    curr->endOfWord = true;
}

// 检查 Trie 中是否存在给定单词
bool search(TrieNode* root, string word) {
    TrieNode* curr = root;
    for (int i = 0; i < word.length(); i++) {
        int index = word[i] - 'a';
        if (curr->children[index] == nullptr) {
            return false;
        }
        curr = curr->children[index];
    }
    return curr->endOfWord;
}

// 检查给定坐标是否在矩阵内部
bool isSafe(int i, int j) {
    return (i >= 0 && i < M && j >= 0 && j < N);
}

// 在 Boggle 矩阵中搜索单词
void searchWord(vector<vector<char>>& board, int i, int j, TrieNode* root, set<string>& words, string currWord) {
    // 检查当前单词是否在 Trie 树中存在
    if (search(root, currWord)) {
        words.insert(currWord);
    }
    // 检查相邻的 8 个单元格，以确定下一个字符
    int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    int y[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
    for (int k = 0; k < 8; k++) {
        int ni = i + x[k];
        int nj = j + y[k];
        // 如果坐标在矩阵内部且未被访问过，则递归搜索
        if (isSafe(ni, nj) && board[ni][nj] != '#' && board[ni][nj] != '*') {
            char temp = board[ni][nj];
            board[ni][nj] = '*';
            searchWord(board, ni, nj, root->children[temp - 'a'], words, currWord + temp);
            board[ni][nj] = temp;
        }
    }
}

// 打印所有找到的单词
void printWords(set<string>& words) {
    for (auto word : words) {
        cout << word << " ";
    }
    cout << endl;
}

// 主函数
int main() {
    vector<vector<char>> board = { {'g', 'i', 'z'},
                                   {'u', 'e', 'k'},
                                   {'q', 's', 'e'} };
    set<string> words;

    // 建立 Trie 树
    TrieNode* root = getTrieNode();
    insert(root, "geek");
    insert(root, "quiz");
    insert(root, "seek");
    insert(root, "guiz");
    insert(root, "size");

    // 在矩阵中搜索所有可能的单词
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            char c = board[i][j];
            if (root->children[c - 'a'] != nullptr) {
                string currWord = "";
                currWord += c;
                board[i][j] = '*';
                searchWord(board, i, j, root->children[c - 'a'], words, currWord);
                board[i][j] = c;
            }
        }
    }

    // 打印所有找到的单词
    printWords(words);

    return 0;
}

在上面的代码中，我们首先构建了一个 Trie 树，然后使用深度优先搜索和回溯法来搜索 Boggle 矩阵中的所有可能单词。在搜索过程中，我们检查当前单元格的相邻单元格，并使用 Trie 树来确定下一个字符是否存在于单词中。如果是，则继续向下搜索；否则，我们回溯到先前的状态并尝试其他路径。最后，我们打印所有找到的单词。