因此，查看有关使用递归解决迷宫的所有其他论坛，他们都没有帮助我解决我的问题。
我从输入文件中得到一个迷宫，并且有一个开始和结束位置。我发现 start 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|
||||||||||