class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i ++ )
            for (int j = 0; j < board[0].size(); j ++ )
                if (board[i][j] == word[0])                     //第一个字母相等，开始bfs搜索
                    if (dfs(board, word, i, j, 0)) return true;

        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, int i, int j, int u)
    {
        //在范围外或者当前字母不相符，则返回false
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[u])
            return false;

        if (u == word.size() - 1) return true;

        board[i][j] = ' ';                                      //置空，防止重复搜索

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        for (int k = 0; k < 4; k ++ )
        {
            int x = i + dx[k], y = j + dy[k];
            if (dfs(board, word, x, y, u + 1)) return true;
        }

        board[i][j] = word[u];                                  //恢复现场

        return false;
    }
};