实现一个单词搜索游戏，给定一个二维网格和一个单词列表，找到单词列表中出现在网格中的所有单词（提示：Trie树 + DFS）。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Trie { // 定义 Trie 树
public:
    Trie* children[26]; // 26 个字母
    bool isEndOfWord; // 当前节点是否为单词结尾

    Trie() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) children[i] = NULL;
    }
};

class Solution {
private:
    vector<string> res; // 存储结果
public:
    void insert(Trie* root, string word) { // 将单词插入到 Trie 树中
        Trie* node = root;
        for (char c : word) {
            if (!node->children[c - 'a']) node->children[c - 'a'] = new Trie();
            node = node->children[c - 'a'];
        }
        node->isEndOfWord = true;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { // WordSearch函数的实现
        Trie* root = new Trie(); // 新建 Trie 树
        for (string word : words) insert(root, word); // 将单词插入 Trie 树中

        int m = board.size(), n = board[0].size(); // 获取矩阵的长和宽
        vector<vector<bool>> visited(m, vector<bool>(n, false)); // 存储访问情况
        string word; // 当前单词

        for (int i = 0; i < m; i++) { // 遍历整个网格，从每个位置开始搜索
            for (int j = 0; j < n; j++) {
                dfs(board, visited, root, word, i, j); // 开始 DFS
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, Trie* node, string& word, int i, int j) { // DFS函数的实现
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j]) return; // 如果当前单元格已经被访问或者越过了边界，则退出DFS
        char c = board[i][j]; // 当前单元格的字母
        if (!node->children[c - 'a']) return; // 如果Trie树中不存在以该字母为开头的单词，则退出DFS

        node = node->children[c - 'a']; // 遍历到Trie树中对应的子节点
        word += c; // 将当前字母加入到字符串中
        if (node->isEndOfWord) { // 判断当前剪枝是否为一个单词的结尾
            res.push_back(word); // 如果是，则将该单词加入结果中
            node->isEndOfWord = false; // 防止出现重复单词
        }

        visited[i][j] = true; // 标记当前单元格已经被访问
        dfs(board, visited, node, word, i - 1, j); // 向上搜索
        dfs(board, visited, node, word, i + 1, j); // 向下搜索
        dfs(board, visited, node, word, i, j - 1); // 向左搜索
        dfs(board, visited, node,
word, i, j + 1); // 向右搜索
        visited[i][j] = false; // 恢复当前单元格状态，避免影响其他的 DFS 流程
        word.pop_back(); // 将当前字母弹出字符串
    }
};

int main() {
    Solution sol;
    vector<vector<char>> board = {{'o','a','a','n'},
                                  {'e','t','a','e'},
                                  {'i','h','k','r'},
                                  {'i','f','l','v'}};
    vector<string> words = {"oath","pea","eat","rain"}; // 单词列表
    vector<string> result = sol.findWords(board, words); // WordSearch函数调用
    for (string s : result) cout << s << " "; // 输出结果
    return 0;
}

class Trie { // 定义 Trie 树
    Trie[] children; // 26 个字母
    boolean isEndOfWord; // 当前节点是否为单词结尾

    public Trie() {
        isEndOfWord = false;
        children = new Trie[26];
    }
}

class Solution {
    List<String> res; // 存储结果

    public void insert(Trie root, String word) { // 将单词插入到 Trie 树中
        Trie node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) node.children[c - 'a'] = new Trie();
            node = node.children[c - 'a'];
        }
        node.isEndOfWord = true;
    }

    public List<String> findWords(char[][] board, String[] words) { // WordSearch函数的实现
        Trie root = new Trie(); // 新建 Trie 树
        for (String word : words) insert(root, word); // 将单词插入 Trie 树中
        int m = board.length, n = board[0].length; // 获取矩阵的长和宽
        boolean[][] visited = new boolean[m][n]; // 存储每个位置的访问情况
        res = new ArrayList<>(); // 初始化结果数组
        StringBuilder word = new StringBuilder(); // 存储当前单词

        for (int i = 0; i < m; i++) { // 遍历整个网格，从每个位置开始搜索
            for (int j = 0; j < n; j++) {
                dfs(board, visited, root, word, i, j); // 开始 DFS
            }
        }
        return res;
    }

    public void dfs(char[][] board, boolean[][] visited, Trie node, StringBuilder word, int i, int j) { // DFS函数的实现
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j]) return; // 如果当前单元格已经被访问或者越过了边界，则退出DFS
        char c = board[i][j]; // 当前单元格的字母
        if (node.children[c - 'a'] == null) return; // 如果Trie树中不存在以该字母为开头的单词，则退出DFS

        node = node.children[c - 'a']; // 遍历到Trie树中对应的子节点
        word.append(c); // 将当前字母加入到字符串中
        if (node.isEndOfWord) { // 判断当前剪枝是否为一个单词的结尾
            res.add(word.toString()); // 如果是，则将该单词加入结果中
            node.isEndOfWord = false; // 防止出现重复单词
        }

        visited[i][j] = true; // 标记当前单元格已经被访问
        dfs(board, visited, node, word, i - 1, j); // 向上搜索
        dfs(board, visited, node, word, i + 1, j); // 向下搜索
        dfs(board, visited, node, word, i, j - 1); // 向左搜索
        dfs(board, visited, node, word, i, j + 1); // 向右搜索
        visited[i][j] = false; // 恢复当前单元格状态，避免影响其他的 DFS 流程
        word.deleteCharAt(word.length() - 1); // 将当前字母从字符串中删除
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] board = {{'o','a','a','n'},
                          {'e','t','a','e'},
                          {'i','h','k','r'},
                          {'i','f','l','v'}};
        String[] words = {"oath","pea","eat","rain"}; // 单词列表
        List<String> result = sol.findWords(board, words); // WordSearch函数的调用
        System.out.println(result); // 输出结果
    }
}