C++ 回溯法求解罗密欧与朱丽叶的迷宫问题

问题描述： 罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条道路。 编程任务： 对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽叶的所有最少转弯道路。

#include 
#include 

using namespace std;

class CMaze
{
public:
	CMaze（int n int m）;
	void ReadData（ifstream& fileIn）;
	void OutPut（ofstream& fileOut）;
	int GetP（）;
	int GetQ（）;
	bool CanPast（int r int l）;
	void Search（int curTurn int curStep int curDir int posX int posY）;
	~CMaze（）;

private:
	int n;
	int m;
	int k;
	int** maze;
	int** path;
	int p q;
	int r s;
	int ans;
	int ans_num;
};

int	dir[9][2] = {{0 0} {-1 0} {1 0} {0 -1} {0 1} {-1 -1} {-1 1} {1 -1} {1 1}};

CMaze::CMaze（int n int m）
{
	this->m = m;
	this->n = n;
	maze = new int*[n];
	for（int i = 0; i < n; i++） maze[i] = new int[m];
	path = new int*[n];
	for（i = 0; i < n; i++） path[i] = new int[m];
	for（i = 0; i < n; i++）
	{
		for（int j = 0; j < m; j++）
		{
			maze[i][j] = path[i][j] = 0;
		}
	}
	ans = this->n * this->m;
	ans_num = 0;
}

CMaze::~CMaze（）
{
	for（int i = 0; i < n; i++） delete[] maze[i];
	delete[] maze;
}

void C