/*
Name: 迷宫类
Copyright:始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
Author:goal00001111
Date: 20-05-10 15:33
Description:
1。建立迷宫（外围建筑围墙），可选择人工创建迷宫或计算机随机创建迷宫，还可修改迷宫
2。设置入口和出口。
3。寻找最短路径，分别采用了广度搜索，深度搜索（包括递归和非递归形式）
4。若找到可行路径，打印路径，否则报告错误。
*/
#include <iostream>
#include <time.h>
using namespace std;
const int M = 20; //最大行数
const int N = 20; //最大列数
enum {OPEN, CLOSE, PASSED, ROAD=-1}; //分别表示该点通，不通，已走和属于所选路径
class MiGong{
struct stype{//存储每个路径点的有关数据；横坐标，纵坐标和其前驱在数组中的位置
int x;
int y;
int pre;//在广度搜索中用来指向前驱，在深度搜索中用来表明目前所指的方向
} way[M*N];
int zx[4];//存储东南西北四个方向所对应的x的值
int zy[4];//存储东南西北四个方向所对应的y的值
int begin[2];//存储入口坐标
int end[2]; //存储出口坐标
int map[M+2][N+2];//存储迷宫地图
int c_map[M+2][N+2];//存储迷宫地图拷贝
public:
MiGong(); //构造函数，建立一个处处都关闭的迷宫
void BuildMiGong(); //建立迷宫地图
void PerfectMiGong();//修正迷宫地图
void CopyMiGong(); //拷贝迷宫地图
void GetBegin();//创建入口坐标
void GetEnd(); //创建出口坐标
bool IsBegin(int x, int y);//判断该点是否为入口
bool IsEnd(int x, int y); //判断该点是否为出口
bool ExtentSearchWay(); //寻找路径：广度搜索
void PutQueue(int rear);//把队列路径显示到迷宫中
bool DeepSearchWay(); //寻找路径：深度搜索
bool Search(int x, int y);//深度搜索递归子函数
bool DeepSearchWay_2(); //寻找路径：深度搜索
void PutStack(int top); //把栈路径显示到迷宫中
void PrintMiGong();//输出迷宫地图
void PrintWay();//输出运动路径
};
MiGong::MiGong()//构造函数，建立一个处处都关闭的迷宫
{
for (int i=0; i<M+2; i++)
for (int j=1; j<=N; j++)
{
if (i==0 || i==M+1)
map[i][j] = j;
else
map[i][j] = CLOSE;
}
for (int i=0; i<M+2; i++)
map[i][0] = i;
for (int i=0; i<M+2; i++)
map[i][N+1] = i;
zx[0]=1; zx[1]=0; zx[2]=-1; zx[3]=0;
zy[0]=0; zy[1]=-1;zy[2]=0; zy[3]=1;
}
void MiGong::GetBegin()//创建入口坐标
{
do{
cout << "请输入入口坐标：" << endl;
cin >> begin[0];
cin >> begin[1];
} while (begin[0]<1 || begin[0]>M || begin[1]<1 || begin[1]>N);
}
void MiGong::GetEnd()//创建出口坐标
{
do{
cout << "请输入出口坐标：" << endl;
cin >> end[0];
cin >> end[1];
} while (end[0]<1 || end[0]>M || end[1]<1 || end[1]>N);
}
bool MiGong::IsBegin(int x, int y)//判断该点是否为入口
{
return (x==begin[0] && y==begin[1]) ? 1 : 0;
}
bool MiGong::IsEnd(int x, int y)//判断该点是否为出口
{
return (x==end[0] && y==end[1]) ? 1 : 0;
}
void MiGong::BuildMiGong() //建立迷宫地图
{
cout << "请选择建立迷宫的方法： 输入m表示人工建立，输入c表示计算机建立" << endl;
char choice;
do{
cin >> choice;
} while (choice != 'm' && choice != 'c');
if (choice == 'm')
{
cout << "请输入迷宫地图，0表示通，1表示不通" << endl;
for (int i=1; i<=M; i++)
for (int j=1; j<=N; j++)
cin >> map[i][j];
}
else
{
srand( (unsigned) time(NULL));
for (int i=1; i<=M; i++)
for (int j=1; j<=N; j++)
map[i][j] = rand() % 2;
}
}
void MiGong::PerfectMiGong()//修正迷宫地图
{
int i, j;
char choice;
do{
do{
cout << "请输入需要修改的坐标：（输入0，0结束）" << endl;
cin >> i;
cin >> j;
} while (i<0 || i>M || j<0 || j>N);
fflush(stdin);
if (i!=0 && j!=0)
{
do{
cout << "打开该点输入o，关闭该点输入c" << endl;
cin >> choice;
fflush(stdin);
} while (choice != 'c' && choice != 'o');
if (choice == 'o')
map[i][j] = OPEN;
else
map[i][j] = CLOSE;
PrintMiGong();
}
} while (i!=0 && j!=0);
}
void MiGong::CopyMiGong()//拷贝迷宫地图
{
for (int i=0; i<M+2; i++)
for (int j=0; j<N+2; j++)
c_map[i][j] = map[i][j];
}
void MiGong::PrintMiGong()//输出迷宫地图
{
for (int i=0; i<M+2; i++)
{
for (int j=0; j<N+2; j++)
{
if (i==0 || i==M+1 || j==0 || j==N+1)
{
if (map[i][j] < 10)
cout << 0;
cout << map[i][j];
}
else if (OPEN == map[i][j])
cout << ' ' << ' ';
else
cout << '#' << '#';
}
cout << endl;
}
}
void MiGong::PrintWay() //输出运动路径
{
int count = 0;
for (int i=0; i<M+2; i++)
{
for (int j=0; j<N+2; j++)
{
if (i==0 || i==M+1 || j==0 || j==N+1)
{
if (c_map[i][j] < 10)
cout << 0;
cout << c_map[i][j];
}
else if (ROAD == c_map[i][j])
{
count++;
cout << char(2) << char(2);
}
else if (OPEN == c_map[i][j])
cout << ' ' << ' ';
else
cout << '#' << '#';
}
cout << endl;
}
cout << "共" << count << "步" << endl;
}
bool MiGong::ExtentSearchWay()//寻找路径：广度搜索
{
CopyMiGong();
int front = 0; //队首
int rear = 0; //队尾
bool find = false; //判断是否找到路径
way[0].x = begin[0];
way[0].y = begin[1];
c_map[way[0].x][way[0].y] = PASSED; //该点已走过
while (front<=rear && !find)
{
for (int i=0; i<4; i++)//判断当前路径点四周是否可通过
{
int x = way[front].x + zx[i];
int y = way[front].y + zy[i];
if (c_map[x][y] == OPEN)//如果某个方向可通过，将该点纳入队列
{
rear++;
way[rear].x = x;
way[rear].y = y;
way[rear].pre = front;
c_map[x][y] = PASSED;
}
if (IsEnd(x, y)) //找到出口
{
PutQueue(rear); //把队列路径显示到迷宫中
find = true;
}
}
front++;
}
return find;
}
void MiGong::PutQueue(int rear) //把队列路径显示到迷宫中
{
CopyMiGong();
int i = rear;
do {
c_map[way[i].x][way[i].y] = ROAD;
i = way[i].pre;
} while (!IsBegin(way[i].x, way[i].y));
c_map[begin[0]][begin[1]] = ROAD;
}
bool MiGong::DeepSearchWay()//寻找路径：深度搜索
{
CopyMiGong();
if (Search(begin[0], begin[1]))
{
c_map[begin[0]][begin[1]] = ROAD;
return true;
}
return false;
}
bool MiGong::Search(int x, int y)//深度搜索递归子函数
{
if (c_map[x][y] != OPEN)//如果某个方向不可通过
return false;
c_map[x][y] = PASSED;
if (IsEnd(x, y)) //找到出口
{
c_map[x][y] = ROAD;
return true;
}
for (int i=0; i<4; i++)//判断当前路径点四周是否可通过
{
if (Search(x+zx[i], y+zy[i]))
{
c_map[x][y] = ROAD;
return true;
}
}
return false;
}
bool MiGong::DeepSearchWay_2()//寻找路径：深度搜索
{
CopyMiGong();
int top = 0; //栈顶指针
bool find = false; //判断是否找到路径
way[0].x = begin[0];
way[0].y = begin[1];
way[0].pre = 0;
c_map[way[0].x][way[0].y] = PASSED; //该点已走过
while (top >= 0 && !find)
{
if (way[top].pre < 4)
{
int x = way[top].x + zx[way[top].pre];
int y = way[top].y + zy[way[top].pre];
if (c_map[x][y] == OPEN)//如果某个方向可通过，将该点纳入栈
{
top++;
way[top].x = x;
way[top].y = y;
way[top].pre = 0;
c_map[x][y] = PASSED;
}
else //否则换个方向
way[top].pre++;
if (IsEnd(x, y)) //找到出口
{
PutStack(top); //把栈路径显示到迷宫中
find = true;
}
}
else
{
top--;
}
}
return find;
}
void MiGong::PutStack(int top) //把栈路径显示到迷宫中
{
CopyMiGong();
while (top >= 0)
{
c_map[way[top].x][way[top].y] = ROAD;
top--;
}
}
int main()
{
MiGong obj;
char choice;
do{
obj.BuildMiGong();
obj.PrintMiGong();
cout << "对迷宫地图还满意吗？选择此迷宫输入y，重新选择迷宫输入n, 修改迷宫输入x" << endl;
do{
cin >> choice;
} while (choice != 'y' && choice != 'n' && choice != 'x');
} while (choice == 'n');
if (choice == 'x') //修正迷宫地图
obj.PerfectMiGong();
obj.GetBegin(); //创建入口坐标
obj.GetEnd(); //创建出口坐标
cout << "广度搜索：" << endl;
if (obj.ExtentSearchWay()) //如果找到迷宫路径
obj.PrintWay(); //输出路径
else
cout << "此路不通！" << endl;
cout << "深度搜索1：" << endl;
if (obj.DeepSearchWay()) //如果找到迷宫路径
obj.PrintWay(); //输出路径
else
cout << "此路不通！" << endl;
cout << "深度搜索2：" << endl;
if (obj.DeepSearchWay_2()) //如果找到迷宫路径
obj.PrintWay(); //输出路径
else
cout << "此路不通！" << endl;
getchar();getchar();
return 0;
}