c语言课程设计迷宫求解.zip

问题描述：以一个m×n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1）, （1,2,2）, （2,2,2） （3,2,3）, （3,1,2）,…。 测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（9,8）为出口。 1 实现提示：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以用二维数组存储迷宫数据，通常设定入口点的下标为（1,1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。

#include 
#include 
#include 
#define ok 1
#define error 0
#define true  1
#define false 0
#define maxrow 10                //最大行数
#define maxrank 10               //最大列数
#define stack_max_size 100       //栈的最大长度
#define stackincrement 10        //栈的增加长度

typedef struct postype{         //迷宫坐标
	int y;                      //纵坐标
	int x;                      //横坐标
}postype; 

typedef struct way{     //通道块储存结构
	int ord;             //通道块在“路径”上的序号
	postype seat;        //通道快在迷宫中的“坐标位置”
	int di;              //从此通道块走向下一个通道块的“方向”
}way;                    //栈的元素结构

typedef struct stack{      //栈结构
	struct way *top;         //栈顶指针
	struct way *base;        //栈底指针
	int stacksize;          //栈的总长度
}stack;

int maze[maxrow][maxrank];    //迷宫数组内容为1表示障碍，0表示通路，2表示走过足迹

int initmaze（postype *s1postype *s2）
//构建迷宫函数
{
	int ij;
	printf（“迷宫为10行10列，请构造迷宫版图（0为通路，1为障碍）：\n“）;
	for（i=0;i<10;i++）
	{
		printf（“\n请输入迷宫第%d行构造：\n“i+1）;
		j=0;
		while（j<10）   
		{
			scanf（“%d“&maze[i][j]）;
		    j++;
		}//while
	}
	printf（“请输入起始坐标（如：2_3）：“）;
	scanf（“%d%d“&s1->x&s1->y）;
	getchar（）;
	printf（“请输入终点坐标（如：2_3）:“）;
	scanf（“%d%d“&s2->x&s2->y）;
	getchar（）;
	printf（“\n迷宫构造完成！\n“）;
	return ok;
}
	
int initstack（stack *s）
//构建一个空栈
{
	s->base=（way*）malloc（stack_max_size*sizeof（way））;
	if（!s->base）   exit（error）;
	s->top=s->base;
	s->stacksize=stack_max_size;
	return ok;
}

int push（stack *sway e）
//将e数据入栈
{
	way *newbase;
	if（s->top-s->base==s->stacksize）                    //若栈满则增加空间
    {
		newbase=（way*）realloc（s->base（s->stacksize+stackincrement）*sizeof（way））;
		if（!newbase）  exit（error）;
		s->base=newbase;
		s->top=s->base+s->stacksize;
		s->stacksize+=stackincrement;
	}
	*s->top++=e;
	return ok;
}

int pop（stack *sway *e）
//若栈不为空，则将栈顶元素出栈并保存到e中
{
	if（s->base==s->top）  return error;       //栈为空错误
	*e=*--s->top;
	return ok;
}

int pass（postype e）
//判断通道块e是否可行，若可行返回ok，不可行返回error
{
	if（maze[e.x][e.y]==0）   return ok;
	else return error;
}

int nextpos（postype *sint di）
//探索下一个通道块坐标，s1为现在坐标，s2返回下一步坐标，di为方向
{
	if（di==1）  s->x++;
	if（di==2）  s->y++;
	if（di==3）  s->x--;
	if（di==4）  s->y--;
    return ok;
}

int stackempty（stack *s）
//判断栈s是否为空，空返回0，不空返回1
{
	if（s->base==s->top）  return 0;
	else return 1;
}

int mazepath（stack *spostype startpostype end）
//迷宫求解函数，start为起始坐标，end为终点坐标
{
	way e;
	postype curpos;     //当前位置
	int curstep=1;      //探索第一步
	curpos=start;       //设置当前位置为起始位置
	if（!initstack（s））  exit（error）;    
	do
	{
		if（pass（curpos））
		{
			maze[curpos.x][curpos.y]=2;      //留下通过足迹
			e.di=1;
			e.ord=curstep;
			e.seat=curpos;
			push（se）;
			if（curpos.x==end.x&&curpos.y==end.y）  return true;    //结束
			nextpos（&curpos1）;
			curstep++;
		}//if
		else
		{
			pop（s&e）;
			while（e.di==4&&stackempty（s））  pop（s&e）;
			if（e.di<4）
			{
				e.di++;
				curpos=e.seat;
                nextpos（&curpose

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2011-01-20 08:57  迷宫求解\
     目录           0  2011-01-20 08:57  迷宫求解\Debug\
     文件       33792  2011-04-24 14:04  迷宫求解\Debug\vc60.idb
     文件       53248  2011-04-24 14:04  迷宫求解\Debug\vc60.pdb
     文件      184378  2011-04-24 14:04  迷宫求解\Debug\迷宫求解.exe
     文件      213924  2011-04-24 14:04  迷宫求解\Debug\迷宫求解.ilk
     文件       10351  2011-04-24 14:04  迷宫求解\Debug\迷宫求解.obj
     文件       43520  2011-04-24 13:43  迷宫求解\Debug\迷宫求解.opt
     文件      186652  2011-04-24 10:03  迷宫求解\Debug\迷宫求解.pch
     文件      451584  2011-04-24 14:04  迷宫求解\Debug\迷宫求解.pdb
     文件        3743  2011-04-24 14:08  迷宫求解\迷宫求解.c
     文件        3425  2011-04-24 12:39  迷宫求解\迷宫求解.dsp
     文件         524  2011-04-24 14:08  迷宫求解\迷宫求解.dsw
     文件       50176  2011-04-24 14:08  迷宫求解\迷宫求解.ncb
     文件       48640  2011-04-24 14:08  迷宫求解\迷宫求解.opt
     文件         752  2011-04-24 14:04  迷宫求解\迷宫求解.plg