时间戳

首页 > 解决方案 > 如果我没有给出起点（源）点和出口点，我该如何解决迷宫？

visual-c++ - 如果我没有给出起点（源）点和出口点，我该如何解决迷宫？

问题描述

我正在尝试解决一个为测试提供不同迷宫的迷宫作业。迷宫的大小会发生变化，并且不会像我在 stackoverflow 中看到的其他示例那样为我提供起始位置或退出位置。我需要帮助如何通过将提供的字符串转换为二维数组来从提供的字符串中选择起点，从而解决迷宫问题。谢谢

这是我迄今为止尝试过的

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


//char** read_maze(string maze, int* rows, int* columns)
//{
//  for (int i = 0; i < maze.length; i++)
//  {
//
//  }
//  char** mymaze = new char*[*rows];
//
//  for (int x = 0; x < *rows; x++)
//      mymaze[x] = new char[*columns];
//
//  for (int i = 0; i < *rows; i++)
//      for (int j = 0; j < *columns; j++)
//          mymaze[i][j] = 1;
//
//  return mymaze;
//}

string solve(string maze)
{
    //find coordinate of starting node!
    int rows = 1, columns = 1;
    char** mymaze;
    mymaze = read_maze(maze, &rows, &columns);



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



    //breadthFirstSearch(maze);

    string output = "";
    //Vertex* current = t;
    /*while (current != s)
    {
        output = current->col + current->row + " " + output;
        current = breadCrumbs[current];
    }*/
    output = maze + " " + output;

    return output;
}

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

    //Vertex* s = vertexSet[];

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

``````````````````````

This are the provided files for testing !
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 


It should print assignment complete to show it runs through all tests.

标签： visual-c++

解决方案

推荐阅读