题解 | #牛群定位系统#

考察知识点：回溯

题目分析：

题目要求在二维数组中找到多个给定的字符串。对于每一个字符串，我们都应该找到递归的入口，即二维数组中与字符串第一个字符相同的那个位置。找到递归的入口后开始进行递归找该字符串的其他部分。

我们可以通过dx和dy枚举上右下左四个方向，在这四个方向中查找是否有我们需要的字符。如果能够匹配，我们记录这个字符已经被访问过，然后继续递归查找下一个字符。

当想要查找的字符的索引越界时，说明整个字符串已经查找完成，可以加入到结果中；如果想要查找的字符在中途没有匹配成功，那么就会回溯。在回溯时应注意恢复现场。

此外，还应该注意结果中不能还有相同的字符串，这要求当我们找到一个匹配的字符串后，应该结束整个递归流程，注意应在恢复现场后结束流程。之后再开始查找下一个字符串。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @param words string字符串vector 
     * @return string字符串vector
     */
    bool dfs(vector<vector<char>> &board, int i, int j, string &des, int index, vector<string> &res, bool st[][15]) {
        int m = board.size();
        int n = board[0].size();
        bool success = false;
        if (index == des.size()) {
            res.push_back(des);
            return true;
        }

        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0, -1};
        for (int x = 0; x < 4; x++) {
            int row = i + dx[x];
            int col = j + dy[x];
            if (row >= 0 && row < m && col >= 0 && col < n && (!st[row][col]) && board[row][col] == des[index]) {
                st[row][col] = true;
                success |= dfs(board, row, col, des, index + 1, res, st);
                st[row][col] = false;
                if (success) return true;
            }
        }
        return false;
    }
    vector<string> findWords(vector<vector<char> >& board, vector<string>& words) {
        // write code here
        vector<string> res;
        int m = board.size();
        int n = board[0].size();
        bool st[15][15] = {false};
        bool success = false;
        for (auto &des: words) {
            char ch = des[0];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == ch) {
                        st[i][j] = true;
                        success |= dfs(board, i, j, des, 1, res, st);
                        st[i][j] = false;
                        if (success) break;
                    }
                }
                if (success) break;
            }
            success = false;
        }
        return res;
    }
};