/**
knakul853
**/
class Solution {
public:
    int dx[4] = {1,0,-1,0};
    int dy[4] ={0,1,0,-1};
    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])
                {
                    board[i][j]='#';
                    if(dfs(board , word , i , j ,1))return true;
                    board[i][j]=word[0];
                }
            }

        return false;
    }

    bool dfs(vector<vector<char>>&board , string word , int i , int j,int len)
    {
        if(len == word.size())return true;

        for(int k=0;k<4;k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];

            if(x<0 || y<0 || x >= board.size() || y >= board[0].size())continue;
            if(board[x][y]!=word[len])continue;
            char temp = board[x][y];
            board[x][y] = '#';

           if(dfs(board , word , x , y , len+1)){
               return true;
           }
            board[x][y] = temp;
        }
        return false;

    }
};