Answer:
#include <cstring>
#include <iostream>
using namespace std;
#define A 3
#define B 3
// LET US CREATE A DICTIONARY
string dict[] = { "KILLS", "GOT", "QUIZ", "GO" };
int n = sizeof(dict) / sizeof(dict[0]);
// Let us make a function to find whether a given word is present in dictionary.
bool isPresent(string& str)
{
// linear search of words
for (int i = 0; i < n; i++)
if (str.compare(dict[i]) == 0)
return true;
return false;
}
// A function for printing all words present on Boggle
void findWordin(char bogle[A][B], bool hasbeenvisited[A][B], int i,
int j, string& str)
{
hasbeenvisited[i][j] = true;
str = str + bogle[i][j];
// If str is in the dictionary, then you need to print it
if (isPresent(str))
cout << str << endl;
// Travering adjacent 8 cells of the boggle
for (int r = i - 1; r <= i + 1 && r < A; r++)
for (int c= j - 1; c <= j + 1 && c < B; c++)
if (r >= 0 && c >= 0 && !hasbeenvisited[r][c])
findWordin(bogle, hasbeenvisited, r, c, str);
// for erasing current characters on the string, and mark them visited
// of the current cells to false
str.erase(str.length() - 1);
hasbeenvisited[i][j] = false;
}
// Prints all words which are in dictionary.
void findWords(char boggle[A][B])
{
// for marking all the characters as not being visited
bool hasbeenvisited[A][B] = { { false } };
// Initializing the present string
string str = "";
// Reading all the characters for finding all the words that begins with the above character
for (int i = 0; i < A; i++)
for (int j = 0; j < B; j++)
findWordin(boggle, hasbeenvisited, i, j, str);
}
// the code for testing of the function
int main()
{
char bogle[A][B] = { { 'k', 'I', 'L' },
{ 'L', 'S', 'M' },
{ 'G', 'O', 'T' } };
cout << "Below list of words are present in the dictionary\n";
findWords(bogle);
return 0;
}
Explanation:
The program is properly commented, and that explains each step of it. However, I have kept dictionary as constant for similifying the code. And it can be set to variable easily, if required.
