Answer :

problemsolver2019

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.

Other Questions