BFS for Maze C++ Segmentation Fault error

Question

I am trying to create a BFS for a maze that will stop when a certain point is reached. While testing it I'm running into a Segmentation fault (core dumped) error. I am trying to modify the code I found on this site. The main differences between what I am trying to do and the code in that site are that I do not need to output the distance traveled so and I am also supposed to output the order in the queue the vertices are in the inside of the matrix. For example, the output should be the following:

What the output of the program should be

The Hashes represent vertices that do not get added to the queue I am not too concerned with them as of now due to this error that is stopping me from going forward.

Here is my code thus far:

#include <queue> 
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define ROW 8
#define COL 11

struct Point{
    int x;
    int y;
};


bool isValid(int x, int y) 
{ 
    // return true if row number and column number 
    // is in range 
    return (x >= 0) && (x< ROW) && 
           (y >= 0) && (y < COL); 
} 

int rowNum[] = {-1, 0, 0, 1}; 
int colNum[] = {0, -1, 1, 0}; 

int BFS(int mat[][COL], Point src, Point dest) 
{ 

    int order = 1;
    // Mark the source cell as visited

   bool visited[ROW][COL];

   memset(visited, false, sizeof visited); 


   visited[src.x][src.y] = true;


    // Create a queue for BFS 
  queue <Point> vertices;

  // Enqueue source cell 

  vertices.push(src);
    // Do a BFS starting from source cell

    while(visited[dest.x][dest.y] != true){

        Point current = vertices.front();

        vertices.pop();

        for (int i = 0; i < 4; i++) 
        { 

            int row = current.x + rowNum[i]; 
            int col = current.y + colNum[i]; 

            // if adjacent cell is valid, has path and 
            // not visited yet, enqueue it. 

            if (isValid(row, col) == true && (mat[row][col]) &&  
               !visited[row][col]) 
            { 
                cout << "Hi" << endl;
                // mark cell as visited and enqueue it 
                visited[row][col] = true;
                mat[row][col] = order;
                order++;
                vertices.push(current);
                cout << vertices.front().x;
                cout << vertices.front().y;
            } 
            else {

            }
        } 
    }

     return -1;
} 

int main() 
{ 

    int mat[ROW][COL] = 
    { 
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 


    }; 

    Point source = {0, 0}; 
    Point dest = {3, 4}; 

    BFS(mat, source, dest);

    for (int i = 0; i < ROW; ++i)
    {
        for (int j = 0; j < COL; ++j)
        {
            std::cout << mat[i][j] << ' ';
        }
        std::cout << std::endl;
    }

    return 0; 
}

I did some troubleshooting beforehand and have found that the error most likely is caused by this spot right here:

if (isValid(row, col) == true && (mat[row][col]) &&  
               !visited[row][col]) 
            { 

                // mark cell as visited and enqueue it 
                visited[row][col] = true;
                mat[row][col] = order;
                order++;
                vertices.push(current);
                cout << vertices.front().x;
                cout << vertices.front().y;
            } 

I assume that because I set up a bunch of output messages (you may notice the cout "Hi's") to occur at certain points in the cause to find the source of the error and that is where it led me.

Any help is appreciated and just to be clear i am trying to find out why i am getting the segmentation fault error.

Thank you.

Answer 1

Ah, one of the best errors in programming, the dreaded segmentation fault! Logging to stdout is one way to debug, but you can make your own life a lot easier by using a debugger (e.g. gdb).

Let's say your executable is called bfs, and it produced a core dump called core.bfs.12345 (12345 was the process's PID). Invoke gdb like this:

$ gdb ./bfs core.bfs.12345

Immediately upon entering, gdb will tell you where your program crashed—no print statements needed! Here's what it should look like:

Program terminated with signal 11, Segmentation fault.
#0  0x0000000000400d3e in BFS (mat=0x7fffffffd950, src=..., dest=...) at ../bfs/bfs.cxx:54
54              Point current = vertices.front();

Essentially, it's telling you to look at line 54 (your line number may be different) where you've called queue<Point>::front(). But, if a queue is empty, calling front() is undefined behavior.

It seems like the rest of your code is pretty much on track. I'd encourage you to rethink the while loop condition. Perhaps, there is a 'safer' way to know whether or not to keep searching.