Thread: Find a word in a 2d grid

  1. #1
    Registered User
    Join Date
    Oct 2004
    Posts
    6

    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

  2. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    247
    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.
    hoping to be certified (programming in c)
    here's the news - I'm officially certified.

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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.
    You're only born perfect.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. please help with binary tree, urgent.
    By slickestting in forum C Programming
    Replies: 2
    Last Post: 07-22-2007, 07:55 PM
  2. I have SDL, where could I find some 2D tutorials?
    By Golden Bunny in forum C++ Programming
    Replies: 1
    Last Post: 04-13-2002, 01:54 PM
  3. Clueless about linked list
    By killerasp in forum C++ Programming
    Replies: 4
    Last Post: 02-14-2002, 11:53 AM