WordBoggle.cpp

/*
 Welcome!
  /\_/\  (
 ( ^.^ ) _)
   \"/  (
 ( | | )
(__d b__)
*/
#include<bits/stdc++.h>
using namespace std;

int xDirection[] = {0 , -1 , -1 , -1 , 0 , 1 , 1 , 1};
int yDirection[] = {-1 , -1 , 0 , 1 , 1 , 1 , 0 , -1};
char boggle[7][7];
bool checkWord(string word , int i , int j , int k , string result , int m , int n)
{
    if(j<0 || k<0 || j>=m || k>=n || i == word.length())
        return false;

    if(result == word)
        return true;
    if(boggle[j][k] == word[i])
    {
        result+=boggle[j][k];
        boggle[j][k] = ' ';
        for(int l = 0 ; l<8 ; l++)
        {
            bool wordExists = checkWord(word , i+1 , j+ xDirection[l] , k + xDirection[l] , result , m , n);
            if(wordExists)
                break;
        }
    }
    else
        return false;

}
int main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    int testCases;
    cin>>testCases;
    while(testCases--)
    {
        int numberOfWords;
        cin>>numberOfWords;
        string dictionary[numberOfWords];
        for(int i = 0 ; i<numberOfWords ; i++)
            cin>>dictionary[i];
        int m , n;
        cin>>m>>n;
        for(int i = 0 ; i<m ; i++)
        {
            for(int j = 0 ; j<n ; j++)
            {
                cin>>boggle[i][j];
            }
        }
        for(int i = 0 ; i<numberOfWords ; i++)
        {
            string word = dictionary[i];
            for(int j = 0 ; j<m ; j++)
            {
                for(int k = 0 ; k<n ; k++)
                {
                    if(boggle[j][k] == word[0])
                    {
                        if(checkWord(word , 0 , j , k , "" , m , n))
                            cout<<word<<" ";
                    }
                }
            }
        }
        cout<<"\n";
    }
    return 0;
}