题解 | #牛群定位系统#

知识点：

DFS/回溯

分析：

我们可以使用回溯算法来解决这个问题。我们从二维牛群定位系统的每个单元格开始，然后通过相邻的单元格递归搜索，构建牛名。如果构建的牛名在单词列表中，则将其添加到结果中。

具体步骤如下：

1. 遍历二维牛群定位系统的每个单元格：

- 对于每个单元格，以该单元格为起点，分别向上、下、左、右四个方向进行深度优先搜索（DFS）。

- 搜索的路径就是构建的牛名。

- 在搜索过程中，需要判断当前构建的牛名是否在单词列表中，如果在则将其添加到结果中。

2. 使用一个集合来存储结果，保证结果中的牛名不重复，并按照在单词列表中出现的顺序进行排序。

3. 返回结果。

编程语言：

C++

ACcode：完整代码

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) {
        std::unordered_set<std::string> result;

        int m = board.size();
        int n = board[0].size();

        for (const std::string& word : words) {
            // 遍历二维牛群定位系统的每个单元格
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
                    // 以每个单元格为起点进行深度优先搜索
                    if (dfs(board, i, j, word, 0, visited)) {
                        result.insert(word);
                    }
                }
            }
        }

        std::vector<std::string> sorted_result;
        for (const std::string& word : words) {
            if (result.count(word) > 0) {
                sorted_result.push_back(word);
            }
        }

        // 按照在单词列表中的顺序进行排序
        std::sort(sorted_result.begin(),
        sorted_result.end(), [&words](const std::string & a, const std::string & b) {
            return std::find(words.begin(), words.end(), a) < std::find(words.begin(),
                    words.end(), b);
        });

        return sorted_result;
    }

  private:
    bool dfs(std::vector<std::vector<char>>& board, int row, int col,
             const std::string& word, int index, std::vector<std::vector<bool>>& visited) {
        if (index == word.length()) {
            return true;
        }

        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() ||
                visited[row][col] || board[row][col] != word[index]) {
            return false;
        }

        visited[row][col] = true;

        bool found = dfs(board, row + 1, col, word, index + 1, visited) ||
                     dfs(board, row - 1, col, word, index + 1, visited) ||
                     dfs(board, row, col + 1, word, index + 1, visited) ||
                     dfs(board, row, col - 1, word, index + 1, visited);

        visited[row][col] = false;

        return found;
    }
};