Возврат лабиринта с использованием рекурсии в Stack Overflow

Итак, просматривая все остальные форумы о решении лабиринта с помощью рекурсии, ни один из них не помог мне с моей проблемой.

Я получаю лабиринт из входного файла, и есть начальная и конечная позиции. Я нахожу стартовый пункт, передавая 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|
||||||||||