c++ - 在 C++ 中使用递归回溯迷宫

Question

所以查看所有其他关于使用递归解决迷宫的论坛，没有一个能帮助我解决我的问题。

我从一个输入文件中得到一个迷宫，并且有一个开始和结束位置。我发现开始 pos 通过引用传递 x 和 y 并递归地解决迷宫。我的问题是迷宫中的每一个可能的地方都被一个标志填满了。当仅应标记解决方案路径时('@' 是我们用来显示解决方案路径的内容)

这是我的代码在编译和运行时输出的内容:

    (2, 1)
    Found Exit
    |||||||||||
    |@@@|||@@@|
    |@|@@@@@|E|
    |||||||||||

    (5, 5)
    Found Exit
    ||||||||||||||||
    |@@@   |NNNN|N||
    |@|@||||N||NNN||
    |@|@@@@@@|||||||
    |@||||||@|E@@  |
    |@|||@@|@|||@|||
    |@|N||@|@@@@@|||
    |@|N||@||||||| |
    |@@@@@@        |
    ||||||||||||||||

    (1, 1)
    ||||||||||
    |NNN||  E|
    ||||||||||

如您所见，“N”是函数发现死胡同并需要回溯并删除它们的地方。 '@' 符号是正确的路径，只是在回溯时不会删除

我相信我的问题是 find_exit 函数或 at_end 函数

代码如下:

// "maze.h"

//header file
#include <iostream>
#include <string>

#ifndef MAZE
#define MAZE

using std::cout;
using std::endl;
using std::cin;
using std::string;


/*
Writes to a string array containing:
* the your (the student author’s) Campus Username (at index 0)
* and Student ID# (at index 1).
Takes as input a pre-existing length-2 string array.
*/
void get_identity(string my_id[]);


/**
Use this to help you enumerate the directions.
Gets passed into one function below.
**/
enum direction
{
    NORTH,
    SOUTH,
    EAST,
    WEST
};


/**
Creates a dynamically allocated array of strings.
Returns a pointer to that array.
**/
string * build_matrix(int rows);


/**
Fills the matrix with one line per string in the array.
Use the getline method.
Why don't you need to send in cols?
**/
void fill_matrix(string *matrix, int rows);


/**
Print the matrix as in the sample_output.txt
**/
void print_matrix(string *matrix, int rows);


/**
Delete the dynamically allocated array of strings.
Why don't you need to send in cols?
**/
void delete_matrix(string *matrix, int rows);


/**
Finds the starting position of Niobe.
Note: x and y are passed by reference; what does this do for you?
Why don't you need cols here? Hint: not the same reason as last two.
**/
void find_start(string *matrix, int rows, int &x, int &y);


/**
This is the recursive backtracking function you need to write.
It should return true if you found the solution,
and false if there is no solution.
It should leave a trail of @ signs along the path to the solution.
Make sure to build your solution with strong emphasis on the pseudocode;
do not try to code it first, first work out the solution on paper/markerboard.
**/
bool find_exit(string *matrix, int x, int y);


/**
Returns true if x and y are the final exit location,
and false otherwise.
**/
bool at_end(string *matrix, int x, int y);


/**
Returns true if the position indexed by x and y is a valid move,
and false otherwise.
What is a valid move?
**/
bool valid_move(string *matrix, int x, int y, direction d);


#endif
#include <fstream>
#include <limits>

using std::ifstream;

void get_identity(string my_id[])
{
    my_id[0] = "sra9wb";
    my_id[1] = "16781948";

    //output
    cout << "MST Campus Username: " << my_id[0] << endl;
    cout << "Student ID: " << my_id[1] << endl;
}

string *build_matrix(int rows)
{
    string *matrix = new string[rows]; //allocating memory for the matrix

    return matrix;
}

void fill_matrix(string *matrix, int rows)
{
    ifstream file_in("sample_input.txt");
    int x = 0;
    int y = 0;
    bool solved = false;

    while (file_in)
    {
        file_in >> rows;

        if (rows == 0)
            return;

        matrix = build_matrix(rows);

        file_in.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); //Grab line until '\n' then toss it

        for (int i = 0; i < rows; i++)
        {
            getline(file_in, matrix[i]);//fillinf matrix with file_in from text file
        }
        find_start(matrix, rows, x, y);
        find_exit(matrix, x, y);
        print_matrix(matrix, rows);
        cout << endl;
        delete_matrix(matrix, rows);
    }
}

void print_matrix(string *matrix, int rows)
{
    for (int i = 0; i < rows; i++) //increment through the row of the matrix
    {
        cout << matrix[i] << endl; //print eack row
    }
}

void delete_matrix(string *matrix, int rows)
{
    delete[] matrix; //delete the matrix
    matrix = NULL;   //set equal to null for no hanging pointers
}

void find_start(string *matrix, int rows, int &x, int &y)
{
    for (int i = 0; i < rows; i++) //increment through the rows
    {
        string column;
        column = matrix[i]; //set the incremented row to string column

        for (int j = 0; j < column.length(); j++) //increment through the length of column
        {
            if (column[j] == 'N') //if the index of column matches N
            {
                x = i; //x is equal to i because of the 1st for loop
                y = j; //y is eqyal to j because of the 1st for loop
            }
        }
    }
    cout << "(" << x << ", " << y << ")" << endl;

}

bool find_exit(string *matrix, int x, int y) //first iteration of function passing in coords of N's starting pos
{
    //check if we reached the end of the maze
    if (at_end(matrix, x, y) == true)
        return true;

    //sets the starting position to @
    matrix[x][y] = 'N';

    //recursive search for out goal
    if (valid_move(matrix, x, y, NORTH) && find_exit(matrix, x - 1, y))
    {
        matrix[x][y] = '@';
        return true;
    }
    else if (valid_move(matrix, x, y, SOUTH) && find_exit(matrix, x + 1, y))
    {
        matrix[x][y] = '@';
        return true;
    }
    else if (valid_move(matrix, x, y, WEST) && find_exit(matrix, x, y - 1))
    {
        matrix[x][y] = '@';
        return true;
    }
    else if (valid_move(matrix, x, y, EAST) && find_exit(matrix, x, y + 1))
    {
        matrix[x][y] = '@';
        return true;
    }

    //this line here is meant to print a space when backtracking occurs
    // matrix[x][y] = ' ';   
    // return false;
}

//this function returns true if you are at the end of the maze
bool at_end(string *matrix, int x, int y)
{
    if (matrix[x][y] == 'E')
    {
        cout << "Found Exit" << endl;
        return true;
    }
    else
        return false;
}

bool valid_move(string *matrix, int x, int y, direction d)
{
    if (d == NORTH)
    {
        //check if north is clear
        if (matrix[x - 1][y] == ' ' || matrix[x - 1][y] == 'E')
            return true;
        else
            return false;
    }
    else if (d == EAST)
    {
        //check if EAST is clear
        if (matrix[x][y + 1] == ' ' || matrix[x][y + 1] == 'E')
            return true;
        else
            return false;
    }
    else if (d == SOUTH)
    {
        //check is south is clear
        if (matrix[x + 1][y] == ' ' || matrix[x + 1][y] == 'E')
            return true;
        else
            return false;
    }
    else if (d == WEST)
    {
        //check if west is clear
        if (matrix[x][y - 1] == ' ' || matrix[x][y - 1] == 'E')
            return true;
        else
            return false;
    }
    else
        return false;
}

//main

// #include "maze.h"



int main()
{
    string *matrix = NULL;
    int rows = 0;

    fill_matrix(matrix, rows);

    return 0;
}

sample_input.txt 文件如下:

4 11
|||||||||||
|   |||   |
|N|     |E|
|||||||||||

10 16
||||||||||||||||
|      |    | ||
| | |||| ||   ||
| |      |||||||
| |||||| |E    |
| |||N | ||| |||
| | || |     |||
| | || ||||||| |
|              |
||||||||||||||||

3 10
||||||||||
|N  ||  E|
||||||||||

0 0

这些是我们应该解决的迷宫。

此外，我不允许编辑头文件。

输出应该是这样的:

    Map 0 -- Solution found:
    |||||||||||
    |@@@|||@@@|
    |N|@@@@@|E|
    |||||||||||

    Map 1 -- Solution found:
    ||||||||||||||||
    |@@@   |    | ||
    |@|@|||| ||   ||
    |@|@@@@@@|||||||
    |@||||||@|E@@  |
    |@|||N@|@|||@|||
    |@| ||@|@@@@@|||
    |@| ||@||||||| |
    |@@@@@@        |
    ||||||||||||||||

    Map 2 -- No solution found:
    ||||||||||
    |N  ||  E|
    ||||||||||

Answer 1

//this line here is meant to print a space when backtracking occurs
        // matrix[x][y] = ' ';   
        // return false;

你为什么不直接取消评论呢？它解决了您的问题，但您必须在程序后手动添加“N”登录起点，因为它会将其替换为“@”或“”(但这很容易)。