Добавляю ли я вершины и ребра правильно для этого лабиринта? - PullRequest
Новая
       2

Добавляю ли я вершины и ребра правильно для этого лабиринта?

0 голосов
/ 04 апреля 2019

Я пытаюсь найти домашнее задание в лабиринте, которое предоставляет другой лабиринт для тестирования. Мне нужна помощь в добавлении краев правильно. Когда я добавляю вершины, а затем проверяю южное местоположение и пытаюсь добавить ребро, эта ошибка Исключение: нарушение прав на чтение. std :: _ Vector_alloc>> :: _ Myend (...) вернул 0x14.

Это то, что я имею до сих пор, оно работает до тех пор, пока не добавит ребра 

#include "solve.h"
#include "vertex.h"


unordered_map<Vertex*, Vertex*> breadCrumbs;
unordered_map<Vertex*, Vertex*> vertexSet;

void breadthFirstSearch(string maze, Vertex* s)
{
    queue<Vertex*> Q;
    unordered_set<Vertex*> marked;

    marked.insert(s);
    Q.push(s);

    while (!Q.empty())
    {
        Vertex* current = Q.front();
        Q.pop();

        for (int i = 0; i < current->neighs.size(); i++)
        {
            Vertex* y = current->neighs[i];
            if (marked.find(y) == marked.end())
            {
                marked.insert(y);
                Q.push(y);
                breadCrumbs[y] = current;
            }
        }
    }
}

void addVertex(int rows, int col, Vertex* A)
{
    Vertex * babyvertex = new Vertex(rows,col);
    vertexSet[A]= babyvertex;
}

//Add a basic (bidirectional) edge connecting a and b
void addEdge(Vertex* a, Vertex* b)
{
    Vertex * aVert = vertexSet[a];  
    Vertex * bVert = vertexSet[b];

    aVert->neighs.push_back(bVert);
    bVert->neighs.push_back(aVert);
}

string solve(string maze)
{
    //Setting the string maze to a 2d array!
    int columns = 0, rows = 0;
    for (int i = 0; i < maze.length(); i++)
    {
        if (maze[i] == '\n')
        {
            columns = i;
            break;
        }
    }
    rows = maze.length() / columns;
    char** MA = new char*[rows];
    for (int i = 0; i < rows; i++)
        MA[i] = new char[columns];

    for (int i = 0; i < rows; i++) 
        for (int j = 0; j < columns; j++)
        {
            MA[i][j] = maze[i*(columns + 1) + j];
        }
    //Starting and exit points to null
    Vertex* s = nullptr;
    Vertex* e = nullptr;
    for (int i = 0; i < columns; i++)
    {
        if (MA[0][i] == ' ')
        {
            s = new Vertex(0, i);
            break;
        }
    }
    for (int i = 0; i < rows; i++)
    {
        if (MA[i][0] == ' ')
        {
            if (s == nullptr)
                s = new Vertex(i, 0);
            else
                e = new Vertex(i, 0);
        }
    }
    for (int i = 0; i < columns; i++)
    {
        if (MA[rows-1][i] == ' ')
        {
            if (s == nullptr)
                s = new Vertex(rows-1, i);
            else
                e = new Vertex(rows-1, i);
        }
    }
    for (int i = 0; i < rows; i++)
    {
        if (MA[i][columns - 1] == ' ')
        {
            if (s == nullptr)
                s = new Vertex(i, columns - 1);
            else
                e = new Vertex(i, columns - 1);
        }
    }

    //add Vertex's

    for (int i = 0; i < rows; i++)
        for (int j = 0; j < columns; j++)
        {
            if (MA[i][j] == ' ')
            {
                Vertex* A = new Vertex(i, j);
                addVertex(i, j, A);
                //add Edges
                //Check North
                if (i + 1 >= 0 || i + 1 < rows)
                {
                    if (MA[i + 1][j] == ' ')
                    {
                        Vertex* B = new Vertex(i + 1, j);
                        addEdge(A, B);
                    }
                }
            }
        }
    /*maze[i + 1][j]
        2
        maze[i - 1][j]
        3
        maze[i + x][j]
        4
        maze[i - x][j]*/

    //breadFirstSearch with maze and starting point
    breadthFirstSearch(maze, s);

    Vertex* current = e;
    while (current->row != s->row && current->col != s->col)
    {
        MA[current->row][current->col] = 'o';
        current = breadCrumbs[current];

    }

    return maze;
}

Это предоставленные файлы для тестирования! main.cpp 

#include <iostream>
#include <cstdlib>
#include <string>
#include "solve.h"

using namespace std;

inline void _test(const char* expression, const char* file, int line)
{
    cerr << "test(" << expression << ") failed in file " << file;
    cerr << ", line " << line << "." << endl;
    abort();
}

#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__))


int main()
{
    // Setup
    srand(2018 + 'f');
    string maze, soln;


    maze = "";
    maze += "##### #\n";
    maze += "#     #\n";
    maze += "# #####\n";
    soln = "";
    soln += "#####o#\n";
    soln += "#ooooo#\n";
    soln += "#o#####\n";
    test(solve(maze) == soln);

    maze = "";
    maze += "##### #\n";
    maze += "#   # #\n";
    maze += "# # # #\n";
    maze += "# #   #\n";
    maze += "# #####\n";
    soln = "";
    soln += "#####o#\n";
    soln += "#ooo#o#\n";
    soln += "#o#o#o#\n";
    soln += "#o#ooo#\n";
    soln += "#o#####\n";
    test(solve(maze) == soln);

    maze = "";
    maze += "########\n";
    maze += "#      #\n";
    maze += "# ## ###\n";
    maze += "#      #\n";
    maze += "## ## ##\n";
    maze += "#  ##  #\n";
    maze += "## ### #\n";
    maze += "## ### #\n";
    soln = "";
    soln += "########\n";
    soln += "#      #\n";
    soln += "# ## ###\n";
    soln += "# oooo #\n";
    soln += "##o##o##\n";
    soln += "# o##oo#\n";
    soln += "##o###o#\n";
    soln += "##o###o#\n";
    test(solve(maze) == soln);

    maze = "";
    maze += "########\n";
    maze += "#  #    \n";
    maze += "# ## ###\n";
    maze += "#      #\n";
    maze += "# # # ##\n";
    maze += "# ###  #\n";
    maze += "#  ### #\n";
    maze += "## #####\n";
    soln = "";
    soln += "########\n";
    soln += "#  #oooo\n";
    soln += "# ##o###\n";
    soln += "#oooo  #\n";
    soln += "#o# # ##\n";
    soln += "#o###  #\n";
    soln += "#oo### #\n";
    soln += "##o#####\n";
    test(solve(maze) == soln);

    maze = "";
    maze += "# ######\n";
    maze += "#  #   #\n";
    maze += "# ## ###\n";
    maze += "#      #\n";
    maze += "# # # ##\n";
    maze += "# ###  #\n";
    maze += "#  ###  \n";
    maze += "########\n";
    soln = "";
    soln += "#o######\n";
    soln += "#o #   #\n";
    soln += "#o## ###\n";
    soln += "#ooooo #\n";
    soln += "# # #o##\n";
    soln += "# ###oo#\n";
    soln += "#  ###oo\n";
    soln += "########\n";
    test(solve(maze) == soln);

    maze = "";
    maze += "########\n";
    maze += "#      #\n";
    maze += "#      #\n";
    maze += "#      #\n";
    maze += "## ## ##\n";
    maze += "## ##  #\n";
    maze += "## ### #\n";
    soln = "";
    soln += "########\n";
    soln += "#      #\n";
    soln += "#      #\n";
    soln += "# oooo #\n";
    soln += "##o##o##\n";
    soln += "##o##oo#\n";
    soln += "##o###o#\n";
    test(solve(maze) == soln);

    maze = "";
    maze += "#########################################################\n";
    maze += "#     #        #  #  #     #  #  #        #     #       #\n";
    maze += "  ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##  \n";
    maze += "#  #     #  #           #           #  #     #     #  # #\n";
    maze += "#########################################################\n";
    soln = "";
    soln += "#########################################################\n";
    soln += "#oooo #ooooooo #  #  #oooo #  #  #ooooooo #oooo #ooooooo#\n";
    soln += "oo##o##o## ##o## ## ##o##o## ## ##o## ##o##o##o##o## ##oo\n";
    soln += "#  #oooo #  #oooooooooo #oooooooooo #  #oooo #oooo #  # #\n";
    soln += "#########################################################\n";
    test(solve(maze) == soln);

    maze = "";
    maze += "# ######################################\n";
    maze += "#   ###     ##                      ## #\n";
    maze += "### ### ### #  ###### ######## #  # #  #\n";
    maze += "# #     # # ##      #        # #### # ##\n";
    maze += "# ####### # ##### # # ###### # #       #\n";
    maze += "#         #     # # #      # # #  ##   #\n";
    maze += "# ### ### ##### # # ######## # #####   #\n";
    maze += "# ### #     #   ###          # ##    ###\n";
    maze += "#     # ### # ######## #######  # #### #\n";
    maze += "# # # # ### #          ##    ## # ## # #\n";
    maze += "# # # #     ########## #   #### # ## # #\n";
    maze += "# # ##### #          # ### #    #      #\n";
    maze += "# #    ## #######  # # #      # ### ####\n";
    maze += "# #### ##   # # #### # #####  #   # #  #\n";
    maze += "# ## ## ###       ## #       ## # # # ##\n";
    maze += "## # #  ###### ## ## ####### ## # # # ##\n";
    maze += "#  # #       # ##                      #\n";
    maze += "###################################### #\n";
    soln = "";
    soln += "#o######################################\n";
    soln += "#ooo###ooooo##                      ## #\n";
    soln += "###o###o###o#  ###### ######## #  # #  #\n";
    soln += "# #ooooo# #o##      #        # #### # ##\n";
    soln += "# ####### #o##### # # ###### # #       #\n";
    soln += "#         #ooooo# # #      # # #  ##   #\n";
    soln += "# ### ### #####o# # ######## # #####   #\n";
    soln += "# ### #     #ooo###          # ##    ###\n";
    soln += "#     # ### #o######## #######  # #### #\n";
    soln += "# # # # ### #oooooooooo##    ## # ## # #\n";
    soln += "# # # #     ##########o#   #### # ## # #\n";
    soln += "# # ##### #          #o### #    #      #\n";
    soln += "# #    ## #######  # #o#      # ### ####\n";
    soln += "# #### ##   # # #### #o#####  #   # #  #\n";
    soln += "# ## ## ###       ## #ooooooo## # # # ##\n";
    soln += "## # #  ###### ## ## #######o## # # # ##\n";
    soln += "#  # #       # ##           ooooooooooo#\n";
    soln += "######################################o#\n";
    test(solve(maze) == soln);

    maze = "";
    maze += "#########################################################\n";
    maze += "     #        #     #     #              #     #         \n";
    maze += "#  #   #    #   # #   # #   #          #   # #   #      #\n";
    maze += "#########################################################\n";
    soln = "";
    soln += "#########################################################\n";
    soln += "ooooo#oooooooo#ooooo#ooooo#oooooooooooooo#ooooo#ooooooooo\n";
    soln += "#  #ooo#    #ooo# #ooo# #ooo#          #ooo# #ooo#      #\n";
    soln += "#########################################################\n";
    test(solve(maze) == soln);

    for (int t = 0; t < 100; ++t)
    {
        // Randomized test to prevent hardcoding
        maze = "";
        maze += "##################################################\n";
        maze += "                                                  \n";
        maze += "#                                                #\n";
        maze += "##################################################\n";
        for (int i = 0; i < 4; ++i)
        {
            int offset = rand() % 5;
            maze[58 + 10 * i + offset] = '#';
            maze[108 + 10 * i + 3 + offset] = '#';
            maze[108 + 10 * i - 1 + offset] = '#';
            soln = maze;
            int j = 51;
            while (j < 101)
            {
                if (soln[j] == '#')
                {
                    soln[j - 1 + 51] = 'o';
                    soln[j - 1 + 52] = 'o';
                    soln[j - 1 + 53] = 'o';
                }
                else
                    soln[j] = 'o';
                ++j;
            }
        }
        test(solve(maze) == soln);
    }

    cout << "Assignment complete." << endl;
}

Vertex.h 

#include <vector>

using namespace std;

// A helper class implementing a vertex in 
// an adjacency-list-based graph.
class Vertex
{
public:
    Vertex(int r, int c)
    {
        row = r;
        col = c;
    }

    // Corresponding row and column location in maze
    int row;
    int col;

    // List of neighboring vertices
    vector<Vertex*> neighs;

};
```````````````````
Solve.h
```````````````````
#ifndef SOLVE_H
#define SOLVE_H

#include <vector>
#include <string>
#include <unordered_set>
#include <queue>
#include <unordered_map>

using namespace std;

string solve(string maze);

#endif

Он должен напечатать задание завершенным, чтобы показать, что он проходит через все тесты.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...