大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

  • 字典树（Trie 树）
  • 深度优先搜索（DFS）
  • 二维数组的遍历和搜索

题目解答方法的文字分析

本题需要在给定的二维牛群定位系统中查找所有可能的牛名，并按照在单词列表中的出现顺序返回。牛名必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个牛名中不允许被重复使用。

为了解决这个问题，我们使用字典树（Trie 树）来保存所有牛的名字，并使用深度优先搜索（DFS）在二维定位系统上查找所有可能的牛名。我们从二维定位系统的每个位置开始，依次向上、向下、向左、向右遍历，每次遍历都检查当前路径是否为某个牛名的前缀，如果是，则继续向下搜索，直到找到完整的牛名。

在代码中，我们先创建一个 Trie 树，并将所有牛的名字插入到 Trie 树中。然后，使用 DFS 在二维定位系统上查找所有可能的牛名。在 DFS 的过程中，我们使用 Trie 树来判断当前路径是否为牛名的前缀，如果是，则将该路径加入结果集。为了避免重复的结果，我们使用 unordered_set 来存储结果。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

class TrieNode {
public:
    bool isEnd;
    TrieNode* children[26];

    TrieNode() {
        isEnd = false;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode();
    }

    // 将单词插入 Trie 树中
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }

    // 判断 Trie 树中是否存在单词
    bool search(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return node->isEnd;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 二维牛群定位系统
     * @param words string字符串vector 所有牛的名字
     * @return string字符串vector 牛名在二维定位系统上出现的顺序
     */
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        int m = board.size();
        int n = board[0].size();

        Trie trie; // 构建 Trie 树
        unordered_set<string> result; // 使用 unordered_set 存储结果，避免重复

        // 将所有牛的名字插入Trie树中
        for (const string& word : words) {
            trie.insert(word);
        }

        // 搜索二维定位系统中的所有可能牛名
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                string path;
                dfs(board, i, j, trie.root, path, result);
            }
        }

        return vector<string>(result.begin(), result.end());
    }

private:
    void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node, string& path, unordered_set<string>& result) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] == '#') {
            return;
        }

        char c = board[i][j];
        int index = c - 'a';
        if (node->children[index] == nullptr) {
            return;
        }

        path.push_back(c);
        node = node->children[index];
        if (node->isEnd) {
            result.insert(path);
        }

        board[i][j] = '#'; // 标记当前位置已访问

        dfs(board, i - 1, j, node, path, result);
        dfs(board, i + 1, j, node, path, result);
        dfs(board, i, j - 1, node, path, result);
        dfs(board, i, j + 1, node, path, result);

        board[i][j] = c; // 恢复当前位置字符
        path.pop_back();
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！