Thread: Searching for particular strings within a 2D array of characters (C)

So I have is a program that reads in a file containing 200,000 and something separate strings and stores them in a 1D array. I also have a 2D grid of max size [300][300] that is being inputted by a user where each character entered is stored in it's own position. For example:

aqcd
efgh
dbcd
mnop

In this [4][4] array.. letter 'a' holds position [0][0] while 'q' holds position [0][1] and so on.

I want to be able to search through the [4][4] grid array and find any strings that are either horizontally, vertically, or diagonally in the grid that are also in my file. Like a word search.

My code is below. Everything works except for searching through the grid and finding the strings. What can I do? Any help would be appreciated.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 301
#define WORDLENGTH 20
#define COLS 300

const int DX_SIZE = 8;
const int DX[] = {-1,-1,-1,0,0,1,1,1};
const int DY[] = {-1,0,1,-1,1,-1,0,1};

int main(void){

int n, a, i, x, r, col, j, k;

FILE* fp1; 
fp1 = fopen("dictionary.txt", "r");
if (fp1 == NULL){
printf("Error while opening file.\n\n");
}

char* w;
char c;
w= malloc(sizeof(char)*WORDLENGTH);
char** grid;
grid = malloc(sizeof(char*)*SIZE);

for(i=0;i<SIZE;i++){
 grid[i] = malloc(sizeof(char)*(COLS+1));
}
    int lines_allocated = 270000;
    int max_line_len = 100;
    /* Allocate lines of text */
    char **words = (char **)malloc(sizeof(char*)*lines_allocated);
    if (words==NULL)
        {
        fprintf(stderr,"Out of memory (1).\n");
        exit(1);
        }
    FILE *fp = fopen("dictionary.txt", "r");
    if (fp == NULL)
        {
        fprintf(stderr,"Error opening file.\n");
        exit(2);
        }

    for (i=0;1;i++)
        {
        /* Have we gone over our line allocation? */
        if (i >= lines_allocated)
            {
            int new_size;
            /* Double our allocation and re-allocate */
            new_size = lines_allocated*2;
            words = (char **)realloc(words,sizeof(char*)*new_size);
            if (words==NULL)
                {
                fprintf(stderr,"Out of memory.\n");
                exit(3);
                }
            lines_allocated = new_size;
            }
        /* Allocate space for the next line */
        words[i] = malloc(max_line_len);
        if (words[i]==NULL)
            {
            fprintf(stderr,"Out of memory (3).\n");
            exit(4);
            }
        if (fgets(words[i],max_line_len-1,fp)==NULL)
            break;
        /* Get rid of CR or LF at end of line */
        for (j=strlen(words[i])-1;j>=0 && (words[i][j]=='\n' || words[i][j]=='\r');j--)
            ;
        words[i][j+1]='\0';
        }
    /* Close file */
    fclose(fp);

    //for(j = 0; j < i; j++)
        //printf("%s\n", words[j]);
 
// Scan in x for the number of input cases
scanf("%d", &x);
for(i=0;i<x;i++){
//Scan in number of rows and cols
scanf("%d %d", &r, &col);
for(j=0;j<r;j++){
 for(a=0;a<col;a++){
  
 int f;
 do f = getchar(); while(isspace(f));
    grid[j][a] = f;
    
   }
}
}

/*printf("%c\n", grid[0][0]);
printf("%s", words[2]);
*/

for(j=0;j<r;j++){
   for(k=0;k<col;k++){
// search through grid
for(i=0;i<DX_SIZE;i++){
 int nextX = grid[r] + DX[i];
 int nextY = grid[col] + DY[i];
 // (nextx, nexty) represents the adjacent location in direction i 
 
}
}
}
*/
 
for(i=0;i<SIZE;i++){
 free(grid[i]); 
}
free(grid);
free(w);
for (;i>=0;i--)
free(words[i]);
free(words);
    
return 0;
}

You don't seem to need dynamic allocation for the grid. And couldn't you process the dictionary one word at a time instead of reading the entire thing into memory?

Code:

  while (fgets(word, sizeof word, fdict)) {
    for (r = 0; r < row; r++) {
      for (c = 0; c < col; c++) {
        for (d = 0; d < NUM_DIRS; d++) {
          // see if word exists in grid at r, c in direction d
        }
      }
    }
  }

I'm not saying that the above is very efficient but I believe it's something like what you were aiming for.

Some other points:
* You should break your program up into functions.
* SIZE should be called ROWS to match COLS. r should be called row (to match col).
* You're opening dictionary.txt twice for no apparent reason.
* There's no need for DX and DY to be global.

BTW, your code as posted doesn't compile due to an extraneous */. Always compile and run your code just before copy/pasting it. Don't just change something by eye, it's too easy to make a mistake!

Observations:

• Some of the code has consistent indentation, while some of it has none.
• You're opening the same file twice (once in the non-indented portion, and once in the indented portion), and only using one of those pointers.
• Inconsistencies within the code (e.g. sometimes casting malloc, and sometimes not).

These are usually signs that the code was "written" by copy/pasting code found on the net. Indeed, the entire indented portion is identical to the code from this old post.

This does not inspire confidence that you understand the copied code (especially with the multi-dimensional allocations taking place). If you do not understand the code, then any suggestions we make will likely not be understood by you.

I suggest you start over, and try solving this problem yourself.