请教下关于罗密欧与朱丽叶迷宫问题

Question

实验名：罗密欧与朱丽叶的迷宫问题 实验内容： 问题描述： 罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条道路。 罗密欧与朱丽叶的迷宫 .编程任务： 对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽叶的所有最少转弯道路。 .数据输入： 由文件input.txt给出输入数据。第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的k行中，每行2 个正整数，表示被封闭的房间所在的行号和列号。最后的2 行，每行也有2 个正整数，分别表示罗密欧所处的方格(p，q)和朱丽叶所处的方格(r，s)。 .结果输出: 将计算出的罗密欧通向朱丽叶的最少转弯次数和有多少条不同的最少转弯道路输出到文件output.txt。文件的第一行是最少转弯次数。文件的第2 行是不同的最少转弯道路数。接下来的n行每行m个数，表示迷宫的一条最少转弯道路。A[i][j]=k表示第k步到达方格(i,j)；A[i][j]=-1 表示方格(i,j)是封闭的。 如果罗密欧无法通向朱丽叶则输出“No Solution!”。 输入文件示例 input.txt 3 4 2 1 2 3 4 1 1 2 2 输出文件示例 output.txt  6 7 1 -1 9 8 2 10 6 7 3 4 5 -1

Answer 1

#include <iostream>
#include <fstream>
using namespace std;
struct RZMaze
{
protected:
static int dir[8][2]; //8个方向
int n, m, k; //行数、列数、封闭房间数
int Romeo[2]; //Romeo所在的位置
int Juliet[2]; //Juliet所在的位置
int **maze; //迷宫数组
int **bestx; //保存最优解
int bestc; //保存最优值
int dirs; //当前拐弯次数
int bccount; //最优解的个数
public:
RZMaze(int nn, int mm, int kk); //构造函数 //给所有的方格标记
~RZMaze(); //析构函数
bool InMaze(int x, int y); //判断坐标(x,y)是否还在迷宫内
void Backtrack(int dep, int x, int y, int di); //递归回溯 走过多少个字 已经拐了多少弯
void ReadData(fstream &fileIn); //从文件中读入数据 
//先读封闭房间的行号和列号写入r,c
void SaveSol(); //保存当前解为最优解
void Process(); //处理函数
void Output(fstream &fileOut); //将计算结果输出到文件中
};
//初始化8个方向的偏移量
int RZMaze::dir[8][2] = {{-1, 0},{-1,1},{0, 1},{1, 1},

{1, 0}, {1, -1}, {0, -1}, {-1, -1}};
RZMaze::RZMaze(int nn, int mm, int kk)
{
int i, j;
n= nn; m = mm; k = kk;
maze = new int* [n];
for(i = 0; i < n; i++) maze[i] = new int [m];
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++) maze[i][j] = 0;
}
bestx = new int* [n];
for(i = 0; i < n; i++) bestx[i] = new int [m];
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++) bestx[i][j] = 0;
}
}
RZMaze::~RZMaze()
{
int i;
for(i = 0; i < n; i++) delete [] maze[i];
delete maze;
for(i = 0; i < n; i++) delete [] bestx[i];
delete bestx;
}
void RZMaze::SaveSol()
{
int i, j;
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++) bestx[i][j] = maze[i]

[j];
}
}
bool RZMaze::InMaze(int x, int y)
{
return x >= 0 && x < n && y >= 0 && y< m;
}
//递归回溯函数，dep表示已经走过了多少个方格，(x,y)为当前坐标，di为已经拐弯的次数
void RZMaze::Backtrack(int dep, int x, inty, int di)
{
int i; int p, q; int tmp;
if(dep == m * n - k && x == Juliet[0] && y == Juliet[1])//找到一个解
{
if(dirs < bestc)
{
bestc = dirs; //更新最优值
bccount = 1; //找到第一个最优解
SaveSol(); //更新最优解
}
else if(dirs == bestc)
{
bccount++; //最优解个数加1
}
return;
}
if(dirs > bestc) return; //找不到更好的解 剪枝
else
{
for(i = 0; i < 8; i++) //8个方向逐一试探
{
p = x + dir[i][0]; q = y + dir[i][1]; //计算下一个位置
if(!InMaze(p, q) || maze[p][q] != 0) //不在迷宫内或者以前来过或者封闭房间
{
continue;
}
tmp = maze[p][q];
maze[p][q] = dep + 1; //下一个走到的位置
if(dep > 1 && di != i) dirs++; //拐弯(第一次探路不算拐弯)
Backtrack(dep + 1, p, q, i); //递归
if(dep > 1 && di != i) dirs--; //撤销
maze[p][q] = tmp;
}
}
}
void RZMaze::Process()
{
bccount = 0; bestc = n * m; dirs = 0;
maze[Romeo[0]][Romeo[1]] = 1;
Backtrack(1, Romeo[0], Romeo[1], 0);
}
void RZMaze::ReadData(fstream &fileIn)
{
int i; int r, c;
for(i = 0; i < k; i++)
{
fileIn >> r >> c;
maze[r - 1][c - 1] = -1; //把封闭房间标记-1
}
fileIn >> r >> c;
Romeo[0] = r - 1; Romeo[1] = c - 1;
fileIn>>r>>c;
Juliet[0] = r - 1; Juliet[1] = c - 1;
}
void RZMaze::Output(fstream &fileOut)
{
int i, j;
if(bccount == 0)
{
cout << "No Solution\n";
fileOut << "No Solution\n";
return;
}
cout << bestc << '\n' << bccount << '\n';
fileOut << bestc << '\n' << bccount << '\n';
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
cout << bestx[i][j] << '\t';
fileOut << bestx[i][j] << '\t';
}
cout << '\n';
fileOut << '\n';
}
}
int main()
{
int n, m, k;
fstream fileIn, fileOut;
fileIn.open("in.txt", ios::in);
fileOut.open("out.txt", ios::out);
if(!fileIn)
{
cout<<"文件打开错误！"<<endl;
return 0;
}
fileIn >> n >> m >> k;
RZMaze r(n, m, k);
r.ReadData(fileIn);
r.Process();
r.Output(fileOut);
return 0;
}