Word Boggle

//{ Driver Code Starts
// Initial template for C++

#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution {
public:
     bool dfs(vector<vector<char> >& board, string &s, int i, int j, int n, int m, int idx){

       if(i<0 || i>=n||j<0||j>=m){
           return false;
       }

       if(s[idx]!= board[i][j]){
           return false;
       }
       if(idx == s.size()-1){
           return true;
       }

       char temp = board[i][j];
       board[i][j]='*';

       bool a = dfs(board,s,i,j+1,n,m,idx+1);
       bool b= dfs(board,s,i,j-1,n,m,idx+1);
       bool c = dfs(board,s,i+1,j,n,m,idx+1);
       bool d = dfs(board,s,i-1,j,n,m,idx+1);
       bool e = dfs(board,s,i+1,j+1,n,m,idx+1);
       bool f = dfs(board,s,i-1,j+1,n,m,idx+1);
       bool g = dfs(board,s,i+1,j-1,n,m,idx+1);
       bool h = dfs(board,s,i-1,j-1,n,m,idx+1);

       board[i][j]=temp;
       return a||b||c||e||f||g||h||d;


   }
   vector<string> wordBoggle(vector<vector<char> >& board, vector<string>& dictionary) {
           int n= board.size();
           int m = board[0].size();
           vector<string> ans;
           set<string> store;
            for(int i=0;i<dictionary.size();i++){
                string s = dictionary[i];
                int l = s.size();
                for(int j = 0 ; j < n;j++){
                    for(int k=0;k<m;k++){
                        if(dfs(board,s,j,k,n,m,0)){
                            store.insert(s);
                        }
                    }
                }
            }

            for(auto i:store){
                ans.push_back(i);
            }

            return ans;

}

};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int N;
        cin >> N;
        vector<string> dictionary;
        for (int i = 0; i < N; ++i) {
            string s;
            cin >> s;
            dictionary.push_back(s);
        }

        int R, C;
        cin >> R >> C;
        vector<vector<char> > board(R);
        for (int i = 0; i < R; i++) {
            board[i].resize(C);
            for (int j = 0; j < C; j++) cin >> board[i][j];
        }
        Solution obj;
        vector<string> output = obj.wordBoggle(board, dictionary);
        if (output.size() == 0)
            cout << "-1";
        else {
            sort(output.begin(), output.end());
            for (int i = 0; i < output.size(); i++) cout << output[i] << " ";
        }
        cout << endl;
    }
}

// } Driver Code Ends