题解 | #牛群定位系统#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @param words string字符串vector 
     * @return string字符串vector
     */
    // 从指定位置开始，是否可以找到制定的字符串，通过index的值来返回
    bool dfs(vector<vector<char>>& board, int x, int y, int index, string& word, vector<vector<int>>& visted) {
        if (index == word.size()) {
            return true;
        }
        int row = board.size(), col = board[0].size();
        if (x < 0 || x >= row || y < 0 || y >= col || word[index] != board[x][y] || visted[x][y]) {
            return false;
        }
        visted[x][y] = 1;
        vector<vector<int>> directions{{0,1}, {1,0},{0,-1},{-1,0}};
        for (int i = 0; i < 4; i++) {
            int new_x = x + directions[i][0];
            int new_y = y + directions[i][1];
            if (dfs(board, new_x, new_y, index+1, word,visted)) {
                return true;
            }
        }
        visted[x][y] = 0;
        return false;
    }
    // 遍历所有位置，判断是否可以找到指定的字符串
    bool exist(vector<vector<char>>& board, string& word) {
        int row = board.size(), col = board[0].size();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                vector<vector<int>> visted(row, vector<int>(col, 0));
                if (dfs(board, i, j, 0, word,visted)) {
                    return true;
                }
            }
        }
        return false;
    }
    vector<string> findWords(vector<vector<char> >& board, vector<string>& words) {
        // write code here
        vector<string> ans;
        for (int i = 0; i < words.size(); i++) {
            if (exist(board, words[i])) {
                ans.push_back(words[i]);
            }
        }
        return ans;
    }
};