BFS для Maze C ++ Ошибка сегментации Ошибка - PullRequest
Новая
       43

BFS для Maze C ++ Ошибка сегментации Ошибка

0 голосов
/ 25 января 2019

Я пытаюсь создать BFS для лабиринта, который остановится, когда будет достигнута определенная точка.Во время тестирования я сталкиваюсь с ошибкой сегментации (ядро сбрасывается).Я пытаюсь изменить код, который я нашел на этом сайте .Основные различия между тем, что я пытаюсь сделать, и кодом на этом сайте в том, что мне не нужно выводить пройденное расстояние, поэтому я также должен вывести порядок в очереди, где вершины находятся внутри матрицы.Например, выходные данные должны быть следующими:

Какой должен быть вывод программы

Хэши представляют вершины, которые не добавляются в очередь, которой я являюсьне слишком озабочен ими на данный момент из-за этой ошибки, которая мешает мне двигаться вперед.

Вот мой код до сих пор: 

#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 "Привет") происходит в определенных точкахпричина, чтобы найти источник ошибки, и это то, куда она меня привела.

Любая помощь приветствуется, и просто чтобы понять, я пытаюсь выяснить, почему я получаю ошибку ошибки сегментации.

Спасибо.

1 Ответ

0 голосов
/ 25 января 2019

Ах, одна из лучших ошибок в программировании, страшная 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();

По сути, это говорит вам о том, чтобы вы посмотрели на строку 54 (ваш номер строки может отличаться), где вы позвонили queue<Point>::front().Но если очередь пуста, вызов front() - это неопределенное поведение .

Похоже, что остальная часть вашего кода в значительной степени на ходу.Я бы посоветовал вам переосмыслить условие цикла while.Возможно, есть «более безопасный» способ узнать, стоит ли продолжать поиск.

...