title: Solving Maze Using BFS in C - Segmentation fault
body: <p>I am attempting to solve a maze using BFS, but I am getting a segmentation fault. Can anyone help me figure out why this is happening? Also if you see anything else wrong with my code? my if statements are to check if the point exists in the maze and that there is a white space at the point. I also am solving the maze using DFS, but the seg fault happens during solve_bfs. Also, everything except solve.c was given to my professor, so the only thing I am suppose to edit is solve.c</p>
  
  <p>Solve.c</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include "maze.h"
  #include "stack.h"
  #include "queue.h"
  
  int solve_bfs(maze * the_maze){
    Queue Q= initQueue();
    enqueue(Q, the_maze-&gt;entry);
    while(!emptyQueue(Q)){
      coord to_explore= dequeue(Q);
      if(to_explore.row == the_maze-&gt;exit.row &amp;&amp; to_explore.col == the_maze-&gt;exit.col){
        print_maze(the_maze);
        free(Q);
        return 1;
      }
      else{
        the_maze-&gt;data[to_explore.row][to_explore.col]= 'o';
  
        if(to_explore.row-1 &gt;= 0){
      if(the_maze-&gt;data[to_explore.row-1][to_explore.col] == ' '){
        coord new;
        new.row= to_explore.row-1;
        new.col= to_explore.col;
        enqueue(Q, new);
      }
        }
        if(to_explore.col+1 &lt; the_maze-&gt;width){
      if(the_maze-&gt;data[to_explore.row][to_explore.col+1]== ' '){
        coord new;
        new.row= to_explore.row;
        new.col= to_explore.col+1;
        enqueue(Q, new);
      }
        }
        if(to_explore.row+1 &lt; the_maze-&gt;height){
      if(the_maze-&gt;data[to_explore.row+1][to_explore.col]== ' '){
        coord new;
        new.row= to_explore.row+1;
        new.col= to_explore.col;
        enqueue(Q, new);
      }
        }
        if(to_explore.col-1 &gt;= 0) {
        if(the_maze-&gt;data[to_explore.row][to_explore.col-1]== ' '){
      coord new;
      new.row= to_explore.row;
      new.col= to_explore.col-1;
      enqueue(Q, new);
        }
        }
      }
      if(emptyQueue(Q)){
      print_maze(the_maze);
      free(Q);
      return 0;
      }
    }
  }
  int solve_dfs(maze * the_maze){
    Stack s= initStack();
    push(s, the_maze-&gt;entry);
    while(!emptyStack(s)){
      coord to_explore= pop(s);
      if(to_explore.row == the_maze-&gt;exit.row &amp;&amp; to_explore.col == the_maze-&gt;exit.col){
        print_maze(the_maze);
        free(s);
        return 1;
      }
      else{
        if(to_explore.row-1 &gt;= 0){
        if(the_maze-&gt;data[to_explore.row-1][to_explore.col]== ' '){
      coord new;
      new.row= to_explore.row-1;
      new.col= to_explore.col;
      push(s, new);
        }
        }
        if(to_explore.col+1 &lt; the_maze-&gt;width){
        if(the_maze-&gt;data[to_explore.row][to_explore.col+1]== ' '){
      coord new;
      new.row= to_explore.row;
      new.col= to_explore.col+1;
      push(s, new);
        }
        }
        if(to_explore.row+1 &lt; the_maze-&gt;height){
        if(the_maze-&gt;data[to_explore.row+1][to_explore.col]== ' '){
      coord new;
      new.row= to_explore.row+1;
      new.col= to_explore.col;
      push(s, new);
        }
        }
        if(to_explore.col-1 &gt;= 0){
        if(the_maze-&gt;data[to_explore.row][to_explore.col-1]== ' '){
      coord new;
      new.row= to_explore.row;
      new.col= to_explore.col-1;
      push(s, new);
        }
        }
      }
      if(emptyStack(s)){
        print_maze(the_maze);
        free(s);
        return 0;
      }
    }
  
  }
  void print_maze(maze * the_maze){
    the_maze-&gt;data[the_maze-&gt;entry.row][the_maze-&gt;entry.col]='S';
    the_maze-&gt;data[the_maze-&gt;exit.row][the_maze-&gt;exit.col]='F';
    for(int i=0; i&lt;the_maze-&gt;width; i++){
      for(int j=0; j&lt;the_maze-&gt;height; j++){
        printf("%s",the_maze-&gt;data[i][j]);
      }
    }
  }
  coord * make_coord(int r, int c){
    coord * coord= malloc(sizeof(coord));
    coord-&gt;row = r;
    coord-&gt;col = c;
    return coord;
  
  }
  void print_coord(coord c){
    printf("(%d,%d)",c.row, c.col);
  }
  </code></pre>
  
  <p>Maze.c </p>
  
  <pre><code>
  #include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include "maze.h"
  
  /**********************************************************
   create_maze
   creates a new maze from the input file characters
  *********************************************************/
  maze * create_maze(FILE *in) {
    // create maze
    maze * new_maze = (maze *) malloc(sizeof(maze));
  
    // read first line of in
    int start_row;
    int start_col;
    int end_row;
    int end_col;
    int num_rows;
    int num_cols;
  
    // start line
    char * line = malloc(sizeof(char)*100);   // start buffer out at 100
    size_t num_read;
  
    getline(&amp;line, &amp;num_read, in);
    if(sscanf(line, "%d %d %d %d %d %d", &amp;num_rows, &amp;num_cols, &amp;start_row, &amp;start_col, &amp;end_row, &amp;end_col) != 6) {
      fprintf(stderr, "Maze file format invalid. Top line must include 6 numbers.\n");
      return NULL;
    }
    // if any are negative values, return NULL
    if(start_row &lt; 0 || start_col &lt; 0 || end_row &lt; 0 || end_col &lt; 0 || num_rows &lt; 0 || num_cols &lt; 0) {
      fprintf(stderr, "Maze file format invalid. Maze file numbers in first row must be non-negative.\n");
      return NULL;
    }
  
    // make sure start_row is in bounds
    if(start_row &gt;= num_rows) {
      fprintf(stderr, "Maze file format invalid. Start row must be &lt; num rows in maze.\n");
      return NULL;
    }
  
    // make sure end_row is in bounds
    if(end_row &gt;= num_rows) {
      fprintf(stderr, "Maze file format invalid. End row must be &lt; num rows in maze.\n");
      return NULL;
    }
  
    // make sure start_col is in bounds
    if(start_col &gt;= num_cols) {
      fprintf(stderr, "Maze file format invalid. Start col must be &lt; num cols in maze.\n");
      return NULL;
    }
  
    // make sure end_col is in bounds
    if(end_col &gt;= num_cols) {
      fprintf(stderr, "Maze file format invalid. Start col must be &lt; num cols in maze.\n");
      return NULL;
    }
  
    // assign maze members
    new_maze-&gt;entry.row = start_row;
    new_maze-&gt;entry.col = start_col;
    new_maze-&gt;exit.row = end_row;
    new_maze-&gt;exit.col = end_col;
    new_maze-&gt;width = num_cols;
    new_maze-&gt;height = num_rows;
  
    // allocate memory for maze data
    new_maze-&gt;data = (char **) malloc(sizeof(char *)*num_rows);
    int i;
    for(i=0; i&lt;num_rows; i++) {
      new_maze-&gt;data[i] = (char *) malloc(sizeof(char)*num_cols);
    }
  
    // get characters from file, one line at a time
    size_t num_vals_read = 0;
    for(i=0; i&lt;num_rows; i++) {
      num_vals_read = getline(&amp;line, &amp;num_read, in);
      if(num_vals_read != num_cols + 1) { //account for newline character
        fprintf(stderr, "Maze file format invalid. Found %d chars on line %d and the width is %d.\n", 
            (num_vals_read-1), i, new_maze-&gt;width);
        return NULL;
      }
      // parse out line
      int j;
      for(j=0; j&lt;num_cols; j++) {
        if(line[j] != ' ' &amp;&amp; line[j] != '*') {
      fprintf(stderr, "Maze file format invalid. Maze file data must contain spaces and stars. Read %c.\n", line[j]);
      return NULL;
        }
        new_maze-&gt;data[i][j] = line[j];
      }
    }
    // try to read more data
    char c;
    if((c = fgetc(in)) != EOF) {
      fprintf(stderr, "Maze file format invalid. Too many characters past %d rows.\n", num_rows);
      return NULL;
    }
  
    free(line);
    return new_maze;
  }
  
  /******************************************************
   free_maze
   frees memory used by the_maze 
   ******************************************************/
  void free_maze(maze * the_maze) {
    // first free the data
    // need to free rows of data, then data
    int i;
    for(i = 0; i &lt; the_maze-&gt;height; i++) {
      free(the_maze-&gt;data[i]);
    }
    free(the_maze-&gt;data);
    free(the_maze);
    return;
  }
  </code></pre>
  
  <p>Queue.c</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include "queue.h"
  
  /* initializes empty queue */
  Queue initQueue() {
    Queue q = malloc(sizeof(QueueType));
    q-&gt;head = 0;
    q-&gt;tail = 0;
    return q;
  }
  
  /* returns 1 if queue is empty and 0 otherwise */
  int emptyQueue(Queue Q) {
    return (Q-&gt;head == Q-&gt;tail);
  }
  /* puts data item d into queue */
  void enqueue(Queue Q, QueueData d) {
    if(full(Q)) {
      printf("Queue is full. Did not add item.\n");
      return;
    }
    Q-&gt;tail++;
    Q-&gt;tail = Q-&gt;tail % MAX_Q; // in case it goes off array
    Q-&gt;data[Q-&gt;tail] = d;
  }
  
  /* removes data item from queue */
  QueueData dequeue(Queue Q) {
    if(emptyQueue(Q)) {
      printf("Attempting to remove from empty queue\n");
      exit(1);
    }
    Q-&gt;head++;
    Q-&gt;head = Q-&gt;head % MAX_Q; // in case it goes off array
    return Q-&gt;data[Q-&gt;head];
  }
  
  /* checks if queue is full */
  int full(Queue Q) {
    return (Q-&gt;tail + 1) % MAX_Q == Q-&gt;head;
  }
  
  /* freeQueue */
  void freeQueue(Queue Q) {
    free(Q);
  }
  </code></pre>
  
  <p>Main.c</p>
  
  <pre><code>
  #include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include "maze.h"
  
  #define NUM_PARAMS 2
  
  /* prototypes */
  void usage(char * executable);
  
  /***********************************************************************
   * main
     executable_name input_filename.txt
     opens input_filename.txt for reading
     creates maze object
     runs the maze solver
     frees maze
  *********************************************************************/
  // function completed for the CS 305 students: DO NOT MODIFY (Unless you find a bug)   
  int main(int argc, char * argv[]) {
    if(argc != NUM_PARAMS) {
      usage(argv[0]);
      return EXIT_FAILURE;
    }    
  
    // open file for reading
    FILE *fp = NULL;
    fp = fopen(argv[1], "r");
    if(fp == NULL) {
      fprintf(stderr, "Error opening input file %s. Exiting.\n", argv[1]);
      return EXIT_FAILURE;
    }
  
    // create maze objects
    // need 2 since we are running BFS on one (which modifies the
    // maze with the path marker character)
    // need clean copy of maze for DFS
    maze * the_maze = create_maze(fp);
    rewind(fp); // resets file pointer to beginning of file
    maze * the_maze2 = create_maze(fp);
  
    // done with file at this point
    fclose(fp);
    fp = NULL;  
  
    // check maze to see if it was created successfully
    if(the_maze == NULL || the_maze2 == NULL) {
      fprintf(stderr, "Error creating maze data structure\n");
      return EXIT_FAILURE;
    }
  
    // run breadth-first-search on maze
    printf("\nSolving using breadth-first search.\n");
    int a = solve_bfs(the_maze);
  
    // run depth-first-search on maze
    printf("\nSolving using depth-first search:\n");
    int b = solve_dfs(the_maze2);
  
    printf("\ncan solve BFS: %d, can solve DFS: %d\n\n", a, b);
  
    // free memory and exit
    free_maze(the_maze);
    free_maze(the_maze2);
    return EXIT_SUCCESS;
  }
  
  /*********************************************************
   usage
   prints error message to user
  **********************************************************/
  void usage(char * executable) {
    printf("Usage: \n%s maze_file.txt\n", executable);
  }
  </code></pre>
  
  <p>stack.c</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include "stack.h"
  
  /* initializes a new stack */
  Stack initStack() {
    Stack s = (Stack) malloc(sizeof(StackType));
    s-&gt;top = NULL;
    return s;
  }
  
  /* empty returns 0 if S is empty and non-zero if S is not empty */
  int emptyStack(Stack S) {
    return (S-&gt;top == NULL);
  }
  
  /* pushes d to S */
  void push(Stack S, StackData d) {
    Node * n = (Node *)malloc(sizeof(Node));
    n-&gt;data = d;
    n-&gt;next = S-&gt;top;
    S-&gt;top = n;
  }
  
  /* pops top item from S */
  StackData pop(Stack S) {
    if(emptyStack(S)) {
      printf("Stack is empty. Attempting to pop an empty stack. Exiting program.\n");
      exit(1);  // exiting program
    }
    // there is data to pop
    StackData toReturn = S-&gt;top-&gt;data;
    Node * tmp = S-&gt;top;  // in order to free this later
    S-&gt;top = S-&gt;top-&gt;next;  // move pointer to next item in stack
    free(tmp);
    return toReturn;
  }
  
  /* frees stack memory */
  void freeStack(Stack S) {
    while(!emptyStack(S)) {
      pop(S);
    }
    free(S);
  }
  </code></pre>
  
  <p>queue.h </p>
  
  <pre><code>
  #ifndef QUEUE_H
  #define QUEUE_H
  
  #include "maze.h"
  
  #define MAX_Q 5000  // 1 more than what can be stored in the queue
                      // in this application, the mazes are on the small
                      // side
  
  /* data to store into queue */
  typedef coord QueueData;  // putting coordinates into queue
  
  /* queue data structure */
  typedef struct QueueTag QueueType;
  typedef struct QueueTag* Queue; // pointer to queue struct
                                  // so when it is passed, the values
                                  // can be updated in functions
  
  struct QueueTag {
    int head;
    int tail;
    QueueData data[MAX_Q]; // space for items in queue
  };
  
  /* function prototypes on queues */
  Queue initQueue();
  int emptyQueue(Queue Q);
  void enqueue(Queue Q, QueueData d);
  QueueData dequeue(Queue Q);
  int full(Queue Q);
  void freeQueue();
  
  #endif
  </code></pre>
  
  <p>maze.h</p>
  
  <pre><code>#ifndef MAZE_H
  #define MAZE_H
  
  /* struct definition for coord */
  typedef struct coord {
    int row;
    int col;
  } coord;
  
  /* struct definition for maze */
  typedef struct maze {
    coord entry;
    coord exit;
    int width;
    int height;
    char ** data;
  } maze;
  
  /* prototypes */
  /* in maze.c */
  maze * create_maze(FILE *in);
  void free_maze(maze * the_maze);
  
  /* in solve.c */
  int solve_bfs(maze * the_maze);
  int solve_dfs(maze * the_maze);
  void print_maze(maze * the_maze);
  coord * make_coord(int r, int c);
  void print_coord(coord c);
  
  #endif
  </code></pre>
  
  <p>stack.h</p>
  
  <pre><code>
  #ifndef STACK_H
  #define STACK_H
  
  #include "maze.h"
  
  #define BAD {-1, -1}  // coordinate off maze
  
  /* data to store into stack */
  typedef coord StackData;  
  
  /* stack data structures */
  typedef struct NodeTag Node;
  typedef struct StackTag StackType;
  typedef struct StackTag* Stack;
  
  /* linked list implementation of stacks */
  struct NodeTag {
    StackData data;
    Node *next;
  };
  
  struct StackTag {
    Node * top;
  };
  
  /* function prototypes on stacks */
  Stack initStack();
  int emptyStack(Stack S);
  void push(Stack S, StackData d);
  StackData pop(Stack S);
  void freeStack(Stack S);
  
  #endif
  </code></pre>