Skip to content

Instantly share code, notes, and snippets.

@zarc1411
Last active March 9, 2020 13:45
Show Gist options
  • Save zarc1411/4d50bd5cbd04b23759448582e27ed78f to your computer and use it in GitHub Desktop.
Save zarc1411/4d50bd5cbd04b23759448582e27ed78f to your computer and use it in GitHub Desktop.
/*
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment