Find a word in a 2d grid

Hi all,

I was asked to make a mystery word game (find some word in a grid to reveal tthe hidden word) and to do this I need to make a function that search for a word in my grid and returns his coordinates and the direction it was found in the grid.

Once the first letter of the searched word matches the grid's letter, the word can be in the 8 directions so we need to check this out.

I have made a function but I'm having problems returning the correct coordinates and direction. If anyone could give a little help pointing me what I'm doing wrong, I would really appreciate !

Here it is:

Code:

---


typedef struct {
          int x;
          int y;
        } TDirection;
       
        // Directions for N, NE, E, SE, S, SW, W, NW, assumming North and West are negative
        TDirection DIRECTION[8] = { { 0,-1 }, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1}, {-1,0}, {-1,-1} };


// The parameters fro this function are the following:
// char* word is the word we are searching for
// char** array is the grid. Each item of the array are string and
//                      represents a line of the grid (note that the grid
//                      will always be square)
// int size is the size of the grid
// int &loc_x, int &loc_y, int &loc_dir are the default coordinates
//  and were initialized to 0 before calling the function
//
bool finWord(char *word, char **array, int size, int &loc_x, int &loc_y, int &loc_dir)
{
          // Get the length of the searched word
          int len = strlen(word);
         
          // A word cannot be only 1 letter
          if(len>1)
          for (int x=0; x < size - 1; x++) {
             
              // We build a new array containing the current line of the grid
              char* arrGrid = new char [strlen(array[x])];
              arrGrid = array[x];
             
              // We go trough the entire line, until we reach a null value
              for (unsigned int y=0; y < strlen(array[x]); y++) {
                    if(tabGrille[y] == '\0') break;
                     
                  // Compare the word's lfirst letter with the current letter in the grid
                    if (toupper(tabGrille[y])!=toupper(word[0]))
                        continue;
               
                  // I think the problem is in this part. I can't seems to make it work properly
                    for (int dir=0; dir<8; dir++) {
                        int cur_x = x;
                        int cur_y = y;
                   
                        // We check the rest of the word in every direction
                        for (int l=0; l<len; l++)  {

                              if (toupper(arrGrid[y])!=toupper(word[0]))
                                  break;
                             
                              if (l==len-1) {
                                  loc_x = x;
                                  loc_y = y;
                                  loc_dir = dir;
                                  cout << "Found the word: " << word << " | position: (" <<
                                  loc_x << "," << loc_y << ") | Direction: " << getDirection(loc_dir) << endl;  // getDirection converts the number into string
                                  return true;
                              }

                              // advance in current direction
                              cur_x += DIRECTION[dir].x;   
                              cur_y += DIRECTION[dir].y;
                             
                                                // ends of the grid
                              if (cur_x<0 || cur_y<0 || cur_x>=size || cur_y>=size)
                                  break; 
                        } 
                    }
              }
          }
    return false;
}

---

Thanks a lot for the help,

Frank

First of...you can't initialize your array of TDirections directly, you will have to do it each element at a time...

Code:

---

// Directions for N, NE, E, SE, S, SW, W, NW, assumming North and West are negative
TDirection DIRECTION[8];

DIRECTION[0].x = 1;
DIRECTION[0].y = 1;

---

Why dont you make it a class instead of a struct.

Here's my initial schema. I had to do this to think things through myself.

Code:

---

Direction Table        coordinate changes from index char
N  = 0                                0, -1
NE = 1                                1, -1                                  N
E  = 2                                  1, 0                          W-|-E
SE = 3                                1, 1                                  S
S = 4                                  0, 1
SW = 5                                -1, 0
W = 6                                  -1, 0
NW = 7                                -1, -1
                                                dx , dy
 
x increases left to right
y increases going down
 
when I think of the size of the grid I think of the total number of squares, so the number of rows would be sqrt(size) as would the number of columns, given that the grid is always a square.  The grid could then be declared using dynamic memory and filled from data in the file or whatever. 
 
My search would then start with something like this:
 
for(x = 0; x < rows; ++x)
  for(y = 0; y < cols; ++y)
          if grid[x][y] == str[0]  //first letter matches grid char
                //screen all 8 directions for str
                if(finWords(str, grid, size, x, y, z))
                  //output x and y coord and direction.
                else
                        //indicate str not found
               
                //terminate program or restart search for another word or let run til end looking for other copies of current word
 
 
with finWords() something like this:
 
bool finWords(char * str, char ** grid, int size, int& loc_x, int& loc_y, int & loc_direct)
{
  for(z = 0; z < 8; ++z)
  {
        switch(loc_direct)
        {
          case 0;
                dx = 0;
                dy = -1;
                break;
          //repeat for cases 1-7
        } 
        if(checkFurther(str, grid, loc_x, loc_y, dx, dy))
                  return true;
  }
  //if no case returned true
  return false;
}
 
and checkFurther() could be something like this:
 
bool checkFurther(char * str, char** grid, int size, int& loc_x, int& loc_y, int dx, int dy)
{
        length = strlen(str);
               
        for(i = 0 ; i < length; ++i)
                curX = loc_x + (i * dx);
                curY = loc_y + (i * dy);
         
                if(!boundsCheck(size, curX, curY))
                  return false;
                if grid[curX][curY] != str[i]
                  return false
 
        return true;
}
 
bool boundsCheck(int size, int curX, curY)
{
        upper = sqrt(size)
        result = true
 
        if curX < 0 or curX >= upper
          result = false
       
  if curY < 0 or curY >= upper
        result = false
 
  return result;       
}

---

My schema varies from yours in:

1) how I interpret the meaning of size
2) how I implement the legend (N/S/E/W)
3) I don't recopy anything from grid, I use the whole grid all the time
4) tabGrille isn't needed because strlen() doesn't count the terminating null char of a C style string.
5) I use a switch statement rather than an array of structs to implement the direction to check.
6) I do bounds checking before checking chars beyond the first char for equality
7) Somehow I managed to get my functions to do be very short and do just one or two things each (not something I'm usually very good at!) which makes evaluating logic and error checking easier.