迷宫问题 - c++编程基础

/*
Name: 迷宫问题
Copyright:
Author:
Date: 11/11/14 08:54
Description:
实现了迷宫找路的广度优先算法，深度优先算法（递归和非递归）。
*/
#include
#include
#define false 0
#define true 1
#define M 9 //最大行数
#define N 9 //最大列数
#define MAXLEN 9999 //最大列数

enum position {OPEN, CLOSE, PASSED, ROAD=-1}; //分别表示该点通，不通，已走和属于所选路径

struct stype{//存储每个路径点的有关数据；横坐标，纵坐标和其前驱在数组中的位置
int x;
int y;
int pre;//在广度搜索中用来指向前驱，在深度搜索中用来表明目前所指的方向
} way[M*N];

int zx[4] = {0, 1, 0, -1};//存储东南西北四个方向所对应的x的值
int zy[4] = {1, 0, -1, 0};//存储东南西北四个方向所对应的y的值
int begin[2];//存储入口坐标
int end[2]; //存储出口坐标
int map[M+2][N+2];//存储迷宫地图
int c_map[M+2][N+2];//存储迷宫地图拷贝
long long sum = 0;

void GetBegin();//创建入口坐标
void GetEnd();//创建出口坐标
int IsBegin(int x, int y);//判断该点是否为入口
int IsEnd(int x, int y);//判断该点是否为出口
void BuildMiGong(); //建立迷宫地图
void PerfectMiGong();//修正迷宫地图
void CopyMiGong();//拷贝迷宫地图
void PrintMiGong();//输出迷宫地图
void PrintWay(); //输出运动路径
int ExtentSearchWay();//寻找路径：广度搜索
int DeepSearchWay();//寻找路径：深度搜索
int Search(int x, int y);//深度搜索递归子函数
int DeepSearchWay_2();//寻找路径：深度搜索
void PutStack(int top); //把栈路径显示到迷宫中
void PutQueue(int rear); //把队列路径显示到迷宫中

int main()
{
char choice;

do
{
BuildMiGong();
PrintMiGong();
puts("对迷宫地图还满意吗？选择此迷宫输入y，重新选择迷宫输入n, 修改迷宫输入x");
do
{
scanf("%c", &choice);
} while (choice != 'y' && choice != 'n' && choice != 'x');
} while (choice == 'n');

if (choice == 'x') //修正迷宫地图
PerfectMiGong();

GetBegin(); //创建入口坐标
GetEnd(); //创建出口坐标

puts("广度搜索：");
if (ExtentSearchWay()) //如果找到迷宫路径
PrintWay(); //输出路径
else
puts("此路不通！");

puts("深度搜索1：");
if (DeepSearchWay()) //如果找到迷宫路径
PrintWay(); //输出路径
else
puts("此路不通！");

puts("深度搜索2：");
if (DeepSearchWay_2()) //如果找到迷宫路径
PrintWay(); //输出路径
else
puts("此路不通！");

return 0;
}

void GetBegin()//创建入口坐标
{
do
{
puts("请输入入口坐标：");
scanf("%d%d", &begin[0], &begin[1]);
} while (begin[0]<1 || begin[0]>M || begin[1]<1 || begin[1]>N);
}

void GetEnd()//创建出口坐标
{
do
{

puts("请输入出口坐标：");
scanf("%d%d", &end[0], &end[1]);
} while (end[0]<1 || end[0]>M || end[1]<1 || end[1]>N);
}

int IsBegin(int x, int y)//判断该点是否为入口
{
return (x==begin[0] && y==begin[1]) ? 1 : 0;
}

int IsEnd(int x, int y)//判断该点是否为出口
{
return (x==end[0] && y==end[1]) ? 1 : 0;
}

void BuildMiGong() //建立迷宫地图
{
int i, j;
puts("请选择建立迷宫的方法：输入m表示人工建立，输入c表示计算机建立");
char choice;

do
{
scanf("%c", &choice);
} while (choice != 'm' && choice != 'c');

//设置边界
for (i=0; i {
map[i][0] = map[i][N+1] = CLOSE;
}
for (j=0; j {
map[0][j] = map[M+1][j] = CLOSE;
}

if (choice == 'm')
{
puts("请输入迷宫地图，0表示通，1表示不通");
for (i=1; i<=M; i++)
for (j=1; j<=N; j++)
scanf("%d", &map[i][j]);
}
else
{
srand( (unsigned) time(NULL));
for (i=1; i<=M; i++)
for (j=1; j<=N; j++)
map[i][j] = rand() % 2;
}
}

void PerfectMiGong()//修正迷宫地图
{
int i, j;
char choice;

do
{
do
{
puts("请输入需要修改的坐标：（输入0，0结束）");
scanf("%d%d", &i, &j);
} while (i<0 || i>M || j<0 || j>N);
fflush(stdin);
if (i!=0 && j!=0)
{
do
{
puts("打开该点输入o，关闭该点输入c");
scanf("%c", &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 CopyMiGong()//拷贝迷宫地图
{
int i, j;
for (i=0; i for (j=0; j c_map[i][j] = map[i][j];
}

void PrintMiGong()//输出迷宫地图
{
int i, j;
for (i=0; i {
for (j=0; j {
if (i==0 || i==M+1)
printf("%02d", j);
else if (j==0 || j==N+1)
printf("%02d", i);
else if (OPEN == map[i][j])
printf(" ");
else
printf("##");
}
p

迷宫问题(一)