GFG PTOD | 01 Feb | Word Search | Medium level | Backtracking

bool solve(vector<vector<char>>& mat, string& word, int i, int j, int widx) {
        int wlen = word.length();
        int n = mat.size();
        int m = mat[0].size();
        //base case
        if(widx == wlen) return true;
        if(i<0 || j<0 || i>=n || j>=m) return false;
        //recursive case
        if(mat[i][j] == word[widx]) {
            bool res = false;
            char tmp = mat[i][j];
            mat[i][j] = '_';
            if(solve(mat, word, i-1, j, widx+1) || solve(mat, word, i+1, j, widx+1) ||
                solve(mat, word, i, j+1, widx+1) || solve(mat, word, i, j-1, widx+1)) 
                    res = true;
            mat[i][j] = tmp;
            return res;
        }
        return false;
    }
    bool isWordExist(vector<vector<char>>& mat, string& word) {
        // Code here
        int n = mat.size();
        int m = mat[0].size();
        int wlen = word.length();
        for(int i=0;i<n; i++) {
            for(int j=0; j<m; j++) {
                if(solve(mat, word, i, j, 0)) return true;
            }
        }
        return false;
    }