题解 | #牛群定位系统#

考察的知识点：深度优先搜索、溯回；

解答方法分析：

1. 定义一个集合sset来存储已经找到的匹配单词，避免重复添加。
2. 定义一个列表ansList来存储最终的答案，即满足条件的单词。
3. 遍历给定的单词数组中的每个单词。
4. 对于每个单词，遍历字符矩阵中的每个位置（通过两个for循环遍历矩阵的行和列，分别用变量i和j表示）。
5. 创建一个二维布尔数组panduan，用于记录字符矩阵中每个位置是否已经被访问过。并将其初始化为全部为true。
6. 调用DFS函数，传入字符矩阵、布尔数组、当前单词、当前位置的行列索引以及当前匹配到的字符的索引（初始为0）。
7. 在DFS函数中，首先判断边界情况：若当前位置超出了字符矩阵的边界、或者当前位置的字符与待匹配的字符不相同、或者当前位置已经被访问过，则返回false。
8. 若当前位置的字符与待匹配的字符相同，并且当前位置没有被访问过，则将当前位置标记为已访问，即将布尔数组对应位置设置为false。
9. 分别在上、下、左、右四个方向上递归地调用DFS函数，继续匹配下一个字符的位置。若四个方向中任意一个方向返回true，则说明找到了匹配的路径，返回true。
10. 若DFS函数返回true，说明当前单词在字符矩阵中有匹配的路径，将当前单词添加到集合sset和列表ansList中。
11. 遍历完所有的单词和字符矩阵中的位置后，将列表ansList转换为数组ans并返回作为最终的答案。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    bool dfs(vector<vector<char>>& board, vector<vector<bool>>& panduan, string s,
             int x,
             int y, int index) {
        if (index == s.length()) {
            return true;
        }
        if (x < 0 || x > board.size() - 1 || y < 0 || y > board[0].size() - 1 ||
                board[x][y] != s[index] || !panduan[x][y]) {
            return false;
        }
        panduan[x][y] = false;
        bool flag1 = dfs(board, panduan, s, x + 1, y, index + 1);
        bool flag2 = dfs(board, panduan, s, x - 1, y, index + 1);
        bool flag3 = dfs(board, panduan, s, x, y + 1, index + 1);
        bool flag4 = dfs(board, panduan, s, x, y - 1, index + 1);
        return flag1 || flag2 || flag3 || flag4;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        unordered_set<string> sset;
        vector<string> ansList;
        for (string p : words) {
            for (int i = 0; i < board.size(); ++i) {
                for (int j = 0 ; j < board[0].size(); ++j) {
                    vector<vector<bool>> panduan(board.size(), vector<bool>(board[0].size(), true));
                    if (dfs(board, panduan, p, i, j, 0) && !sset.count(p)) {
                        sset.insert(p);
                        ansList.push_back(p);
                    }
                }
            }
        }
        return ansList;
    }
};