class Solution {
public:
    //dfs+剪枝
    int row,col;
    bool dfs(vector<vector<char>>& board,string word,int i,int j,int k){
        if(i<0 || i>=row || j<0 || j>=col || board[i][j]!=word[k]){
            return false;
        }
        board[i][j]='/0';       //防止遍历回去
        int dx[]={-1,0,1,0};	//静态数组大括号{}
        int dy[]={0,1,0,-1};
        bool res;
        for(int t=0;t<4;t++){
            bool tmp=dfs(board,word,i+dx[t],j+dy[t],k+1);
            res=tmp;
            if(res){
                break;
            }
        }
        if(k==word.length()-1){
            return true;
        }
        board[i][j]=word[k];        //恢复现场
        return res;
    }
    bool exist(vector<vector<char>>& board, string word) {
        row=board.size();
        col=board[0].size();
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(dfs(board,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
};