c++ - BFS for Maze C++ 段错误

Question

我正在尝试为一个迷宫创建一个 BFS，该迷宫将在到达某个点时停止。在测试它时，我遇到了段错误(核心转储)错误。我正在尝试修改我在此 site 上找到的代码.我正在尝试做的事情与该站点中的代码之间的主要区别是我不需要输出行进的距离，而且我还应该输出队列中的顺序，顶点位于矩阵的内部。例如，输出应如下所示:

What the output of the program should be

哈希表示没有添加到队列中的顶点，由于这个错误阻止我继续前进，我现在不太关心它们。

到目前为止，这是我的代码:

#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; 
}

我事先做了一些故障排除，发现错误很可能是由这里的这个地方引起的:

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;
            } 

我假设因为我设置了一堆输出消息(您可能会注意到 cout“Hi's”)出现在原因的某些点以找到错误的来源，这就是它引导我的地方。

任何帮助表示赞赏，只是为了清楚起见，我正试图找出我收到段错误的原因。

谢谢。

Answer 1

啊，编程中最好的错误之一，可怕的segmentation fault !记录到 stdout是一种调试方法，但您可以使用调试器(例如 gdb)让自己的生活变得更轻松。

假设您的可执行文件名为 bfs , 它产生了一个名为 core.bfs.12345 的核心转储(12345 是进程的 PID)。调用 gdb像这样:

$ gdb ./bfs core.bfs.12345

进入后立即gdb会告诉您哪里您的程序崩溃了——不需要打印语句!它应该是这样的:

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();

本质上，它告诉您查看您调用了 queue<Point>::front() 的第 54 行(您的行号可能不同) .但是，如果队列为空，则调用 front()是未定义的行为。

您的其余代码似乎都已步入正​​轨。我鼓励您重新考虑 while循环条件。或许，有一种“更安全”的方式来判断是否继续搜索。