题解 | #童谣寻找问题#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    vector<vector<int>> directions{{1,0}, {-1,0}, {0,1}, {0,-1}};
    void backtrace(vector<vector<char>>& board, string& word, int depth, bool& flag, int x, int y, vector<vector<int>>& vis) {
        if (flag) return;
        if (depth == word.size()) {
            flag = true;
            return;
        }
        int row = board.size(), col = board[0].size();
        for (int i = 0; i < 4; i++) {
            int new_x = x + directions[i][0];
            int new_y = y + directions[i][1];
            if (new_x >= 0 && new_x < row && new_y >= 0 && new_y < col && board[new_x][new_y] == word[depth] && vis[new_x][new_y] == 0) {
                vis[new_x][new_y] = 1;
                backtrace(board, word, depth+1, flag, new_x, new_y, vis);
                vis[new_x][new_y] = 0;
            }
        }
    }

    bool exist(vector<vector<char> >& board, string word) {
        // write code here
        int row = board.size(), col = board[0].size();
        bool flag = false;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (flag) break;
                if (board[i][j] = word[0]) {
                    vector<vector<int>> vis(row, vector<int>(col, 0));
                    vis[i][j] = 1;
                    backtrace(board, word, 1, flag, i, j, vis);
                }
            }
            if (flag) break;
        }
        return flag;
    }
};