Input:  grid[][] = {"axmy",
                    "bgdf",
                    "xeet",
                    "raks"};
Output: Yes
a x m y
b g d f
x e e t
r a k s
Input: grid[][] = {"axmy",
                   "brdf",
                   "xeet",
                   "rass"};
Output : No

The general idea of what output should be. I have already coded the grid:

# include <stdio.h>
# include <math.h>
# include <stdlib.h>
int x;
int y;
char grid [10] [10];
int z;
int j;
int main()
{
// declare array with alphabet
  char alphabet[26] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g',
                        'h', 'i', 'j', 'k', 'l', 'm', 'n',
                        'o', 'p', 'q', 'r', 's', 't', 'u',
                        'v', 'w', 'x', 'y', 'z' };
printf ("Insert the width (x) and height (y) of the grid \n");
scanf ("%d %d", &x, &y);
for (z = 0; z < x; z++)
 {
  for (j=0; j < y; j++)
  {
   // print letters instead of dots
   grid [z] [j] = alphabet[rand() % 26];
  }
  }
for (z = 0; z < x; z++)
 {
  for (j=0; j < y; j++)
  {
   printf ("%c", grid [z] [j]);
  }
  printf ("\n");
  }
}

Recommended Answers

All 14 Replies

Think about how you would do this with a pen and paper...
You're going to have to start at each point in the grid and search in up to 8 directions to look for words.
Expect a lot of nested loops!

Yes, I don't know how to code this

I need help to get started.

Switch off your computer. Get a paper and a pencil.
Draw a letter grid and find all the words in it.
Write down exactly how you did that (you may need to do it a few times before you get this right - you need to get every step documented).
Now turn the computer back on and convert what you just wrote into code.

Don't be discouraged. At the beginning you won't be able to see the whole thing. Just make a start and keep going until it's done.

Nobody can do this for you. It's called "learning", and it's worth all the effort.

commented: Old school! +15

Check every cell, if the cell has first character, then recur one by one and try all 4 directions from that cell for a match.
Mark the position in the grid as visited and recur in the 4 possible directions.
After recurring, again mark the position as unvisited.
Once all the letters in the word is matched, return true.

Thank you for replying. I know I have to use the recursive function. There are the steps that I will have to code.

That's a great start. Let us know how you get on with converting that into code.

ps: You didn't say whether the word has to be in a straight line in the grid, or if it can zig-zag.
If its the first case (as in your examples) then the solution is a lot simpler.

its horizontal, vertical and diagonal

In that case there's no need for marking visited, nor for recursion.
Simply for each square check the horizontal, vertical and diagonal directions until a word is found or you hit the edge.
That's basically 8 loops inside a row/col double loop, but with a bit of cunning you can generalise those 8 into one with suitable parameters.

This is what i wrote still has errors though.

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

using namespace std;

int n;
char grid [10] [10];
int z;
int j;

bool dfs(int grid[][], bool **visited, char word[], int ind, int x, int y){
    //This means we have reached the end of word
    if(word[i] == '\0') return true;

    if(x<0 || x>=n) return false;

    if(y<0 || y>=n) return false;

    if(word[x][y]!= word[i]) return false;

    if(visited[x][y]) return false;

    visited[x][y] = true;

    bool success = false;

    for(int i=x-1; i<=x+1; i++){
        for(int k = y-1; y<=y+1;k++){

            success =dfs(grid, visited, word,ind+1,i,k)
            if (success) break;
        }
        if (success) break;

    }

    visited[x][y] = false;

    return success;
}
}

int main()
{

    bool found = False;
    char word[n*n];
    // declare an array with alphabet
    char alphabet[26] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g',
                          'h', 'i', 'j', 'k', 'l', 'm', 'n',
                          'o', 'p', 'q', 'r', 's', 't', 'u',
                          'v', 'w', 'x', 'y', 'z' };

    bool **visited;
    n=5;
    for (z = 0; z < n; z++)
    {
        for (j=0; j < n; j++)
        {
          // print letters
          grid [z] [j] = alphabet[26][rand() % 26];
          cout<<grid [z] [j]<<" ";
        }
        cout<<endl;
    }

    //The visited array is the make sure there are no duplicate letters from the grid
    visited = new bool*[n];
    for(z=0;z<n;z++){
        visited[z] = new bool[n];
        for(j=0;j<n;j++){
            visited[z][j] = False;
        }
    }

    cout<<"Enter the word to search for: ";
    cin>>word;

    for (z = 0; z < n; z++)
    {
        for (j=0; j < n; j++)
        {
            if(word[z][j] == word[0]){
                visited[z][j] = true;
                found = dfs(grid,visited,word,i, z,j)
                visited[z][j] = false;
            }
            if(found) break;
        }
        if(found) break;
    }
}

If you have errors then fix them. If you wan't more help then tell us what errors you are getting. I can see several but I think you could go to the trouble of adding more information.

I fixeed the errors, the program outputs a grid now and asks user to enter words but does not output if it exists in the grid or not.

image1.png

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

using namespace std;

int n;
char grid [10] [10];
int z;
int j;

bool dfs(char grid[5][5], bool visited[5][5], string word, int ind, int x, int y){
    //This means we have reached the end of word
    if(word[ind] == '\0') return true;

    if(x<0 || x>=n) return false;

    if(y<0 || y>=n) return false;

    if(grid[x][y]!= word[ind]) return false;

    if(visited[x][y]) return false;

    visited[x][y] = true;

    bool success = false;

    for(int i=x-1; i<=x+1; i++){
        for(int k = y-1; y<=y+1;k++){

            success =dfs(grid, visited, word,ind+1,i,k);
            if (success) break;
        }
        if (success) break;

    }

    visited[x][y] = false;

    return success;
}

int main()
{

    bool found = false;
    string word;
    // declare an array with alphabet
    char alphabet[26] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g',
                          'h', 'i', 'j', 'k', 'l', 'm', 'n',
                          'o', 'p', 'q', 'r', 's', 't', 'u',
                          'v', 'w', 'x', 'y', 'z' };

    bool visited[5][5];
    char grid[5][5];
    n=5;
    for (z = 0; z < n; z++)
    {
        for (j=0; j < n; j++)
        {
          // print letters
          grid [z] [j] = alphabet[rand() % 26];
          cout<<grid [z] [j]<<" ";
        }
        cout<<endl;
    }

    //The visited array is the make sure there are no duplicate letters from the grid
    //visited = new bool*[n];
    for(z=0;z<n;z++){
       // visited[z] = new bool[n];
        for(j=0;j<n;j++){
            visited[z][j] = false;
        }
    }

    cout<<"Enter the word to search for: ";
    cin>>word;

    for (z = 0; z < n; z++)
    {
        for (j=0; j < n; j++)
        {
            if(grid[z][j] == word[0]){
                visited[z][j] = true;
                found = dfs(grid,visited,word,0, z,j);
                visited[z][j] = false;
            }
            if(found) break;
        }
        if(found) break;
    }
}

I need help to add the lines somehwere in my code so when the user enters the word, the program checks if the word is found or not and outputs it.

 cout << "'" << word << "' was found in the grid" << endl;
 cout << "'" << word << "' was not found in the grid" << endl;
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.