d）输出通路迷宫问题（迷宫问题）

本文目录

• 迷宫问题
• 急求：C语言实现的迷宫问题代码！
• 迷宫求解
• 跪求高手 数据结构迷宫问题
• 数据结构迷宫问题（c语言）
• 用数据结构解迷宫
• 迷宫问题，C语言
• 数据结构C语言版的迷宫问题如何解决
• 寻求计算机专业编程：1迷宫问题的求解，要求生成迷宫矩阵，求出迷宫最短的通路（数据结构原代码）

迷宫问题

概要设计
1． 设计栈的抽象数据类型定义：
ADT Stack{
数据对象：D={ai|ai∈CharSet,i=1,2..,n}
数据关系:R1={《ai-1,ai》|ai-1,ai∈D,i=2,...,n}
基本操作:(这里仅列举本题中使用的操作)
Creat()
操作结果:构建一个空栈。
Push()
操作结果:在栈顶插入新的元素。
Pop（）
操作结果：将栈顶元素弹出。
Empty（）
判断栈是否为空
}ADT stack
2． 本程序包含了三个模块
1） 主程序模块：
void main()
{
输入起点，终点；
处理命令；
输出结果；
}
2） 栈模块-----实现栈抽象数据类型
3） 迷宫模块-----找出迷宫中的通路
3.求解迷宫中一条通路的伪码
设定当前位置的初值为入口位置:
do{
若当前位置可通,
则{ 将当前位置插入栈顶; //纳入路径
若该位置是出口,则输出迷宫图,结束; //求得路径存放在栈中
否则切换当前位置的东邻方块为新的当前位置;
}
否则{
若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；
若栈不空但栈顶位置四周均不可通，
则{删去栈顶位置； //后退一步，从路径中删去该通道
若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；
}
}
}while（栈不空）
（栈空说明没有路径存在）
三. 详细设计
迷宫坐标位置类型
typedef struct maze{
int a;
int b;
int dir;
struct maze *next;
}mazestack;
栈的基本操作实现
1） 栈的初始化
mazestack *creat(){
mazestack * p;
p=(mazestack *)malloc(sizeof(mazestack)); //开辟坐标空间
if(!p)
return NULL; //开辟失败，返回空值
p-》next=NULL;
return p; //返回栈顶指针
}
2） 压栈操作
mazestack * push(mazestack * p,int i,int j,int k) //p为栈顶指针
i , j为坐标参数，k为通路下一步方向代码
{
mazestack * p1;
p1=(mazestack *)malloc(sizeof(mazestack)); //开辟坐标空间
if(!p1)
return NULL;
p1-》a=i;
p1-》b=j;
p1-》dir=k; //将参数导入坐标空间
p1-》next=p; //将新开辟空间压入栈
p=p1; //移动栈顶指针到新栈顶
return p; //返回栈顶指针
}
3） 弹栈操作
mazestack * pop(mazestack *p, int *i,int *j,int *k) // p为栈顶指针，i，j为坐标参数，k为通路下一步方向代码
{
mazestack *p1;
p1=p;
*i=p1-》a;
*j=p1-》b;
*k=p1-》dir; //将空间中坐标和方向代码导出
p=p-》next; //将栈顶指针移动到新栈顶位置
free(p1); //释放旧栈顶空间
return p;
}
4） 判断栈空
int empty(mazestack *p) //p为所要判断的指针
{
if(p-》next==NULL){
return 1; //栈空，返回1
}
else return 0; /栈不空，返回0
}
改变路径前进方向
int nextpos(int *i,int *j,int di) //i，j为迷宫坐标，di为下一步路径的方向
{
switch(di){
case 1: *i=*i;*j=*j+1;break; //di=1 ，下一步向东
case 2: *i=*i+1;*j=*j;break; //di=2 ，下一步向南
case 3: *i=*i;*j=*j-1;break; //di=3 ， 下一步向西
case 4: *i=*i-1;*j=*j;break; //di=4 ， 下一步向北
}
return 1;
}
求迷宫路径的算法
mazestack * maze(int i1,int j1,int i2,int j2) //i1，j1为入口坐标，i2，j2为出口坐标
{
int a={ 0,0,0,0,0,0,0,0,0,0,
0,1,1,0,1,1,1,0,1,0,
0,1,1,0,1,1,1,0,1,0,
0,1,1,1,1,0,0,1,1,0,
0,1,0,0,0,1,1,1,1,0,
0,1,1,1,0,1,1,1,1,0,
0,1,0,1,1,1,0,1,1,0,
0,1,0,0,0,1,0,0,1,0,
0,0,1,1,1,1,1,1,1,0,
0,0,0,0,0,0,0,0,0,0}; //具体迷宫形式
int i=i1,j=j1;
int k;
mazestack * p;
p=creat(); //建立栈
do{
if(a==1){ //判断路径是否已经经过
a=5; //没有经过，则将该坐标进行标记
p=push(p,i,j,a); //将该坐标点压入栈中
if(i==i2&&j==j2){ //判断压入坐标是否为终点
for(i=0;i《10;i++){
for(j=0;j《10;j++){
if(a》1){
a=5;
printf(" %d ",a);
}
else printf(" %d ",a);
}
printf("\n\n");
} //压入坐标是终点，将走迷宫图输出，其中路径值为5

return p; //返回栈顶指针
}
nextpos(&i,&j,1); //压入坐标不是终点，将坐标点向东移动一步
}
else{ //路径已经经过
if(!empty(p)){
p=pop(p,&i,&j,&k); //退回一步
a=k;
while(a==4&&!empty(p)) //判断该坐标周围是否还有通路
{
a=1;
p=pop(p,&i,&j,&k);
a=k; //没有通路，将其坐标置回成没有经过的路，退回到上一步
}
if(a《4){
a++;
p=push(p,i,j,a);
nextpos(&i,&j,a);
} //存在通路，则向下一步方向前进
else if(a》4){
a=2;
p=push(p,i,j,a);
nextpos(&i,&j,a);
} //只经过一次的通路，下一步向南走
}
}
}while(!empty(p)) ;
return NULL;
}
主函数算法
main()
{
int i1,i2,j1,j2;
int m,n,l;
int num=0;
mazestack * ma;
printf("input start point\n");
scanf("%d,%d",&i1,&j1); //输入起点
printf("input end point\n");
scanf("%d,%d",&i2,&j2); //输入终点
ma=maze(i1,j1,i2,j2); //求解迷宫
if(ma==NULL){
printf("There is no way");
} //空栈，说明没有路经
else{
while(!empty(ma)){
ma=pop(ma,&m,&n,&l);
printf("(%d,%d) ",m,n);
num++;
} //输出路径结果和步长
printf("the step is %d",num);
}
}
以上的分析只是包含了四个方向,如果要走八个方向的迷宫,这个只是改那个路径的地方就可以了.剩余的任务就有待你自己解决了.

急求：C语言实现的迷宫问题代码！

#include 《stdio.h》
#include 《stdlib.h》
#include 《malloc.h》
struct node
{
int sign;//标识,0什么都不在,1在open中,2在closed中
int flag;//标志位 0/1,0可以走,1不可以走
int f,g,h;//判断函数
int x,y;//坐标
int old;//是否old节点,0非,1是
};
struct link
{
node fnode;
link *next;
link *pri;
};
link *open,*closed,*bestnode,*successor,*p,*q,*r,*s;
int maze_flag={ {0,1,0,0,0,0,0},
{0,1,0,1,0,1,0},
{0,1,0,0,0,1,0},
{0,1,0,1,0,1,0},
{0,0,0,1,0,0,0},
{1,1,0,1,0,1,0},
{0,0,0,0,0,1,0}};//表示迷宫的数组,0可以走,1不可以走
node maze;
int judge(node n)//判断函数,判断n节点是否可以走
{
if(n.flag==1)
return(1);
else
return(0);
}
void in_open(node n)//将n节点放入open表
{
p=open;
while(p-》next!=open)
{
if(n.f》=p-》fnode.f)
{
p-》next-》pri=(link *)malloc(sizeof(link));
p-》next-》pri-》pri=p;
p=p-》next;
p-》pri-》next=p;
p-》pri-》pri-》next=p-》pri;
p=p-》pri;
p-》fnode.flag=n.flag;
p-》fnode.f=n.f;
p-》fnode.g=n.g;
p-》fnode.h=n.h;
p-》fnode.x=n.x;
p-》fnode.y=n.y;
p-》fnode.old=n.old;
p-》fnode.sign=n.sign=1;
}
else
p=p-》next;
}
open-》pri=(link *)malloc(sizeof(link));
open-》pri-》pri=p;
open-》pri-》next=open;
p-》next=open-》pri;
p=p-》next;
p-》fnode.flag=n.flag;
p-》fnode.f=n.f;
p-》fnode.g=n.g;
p-》fnode.h=n.h;
p-》fnode.x=n.x;
p-》fnode.y=n.y;
p-》fnode.old=n.old;
p-》fnode.sign=n.sign=1;
}
void out_open(node n)//将n节点从open表中移出
{
p=open;
while(p-》next!=open)
{
if(n.f=p-》fnode.f)
{
link *p1;
p1=p-》next;
p-》next=p-》next-》next;
p-》next-》pri=p;
free(p1);
n.sign=0;
}
else
p=p-》next;
}
}
void in_closed(node n)//将n节点放入closed表
{
while(q-》next!=closed)
{
if(n.f》=q-》fnode.f)
{
q-》next-》pri=(link *)malloc(sizeof(link));
q-》next-》pri-》pri=q;
q=q-》next;
q-》pri-》next=p;
q-》pri-》pri-》next=q-》pri;
q=q-》pri;
q-》fnode.flag=n.flag;
q-》fnode.f=n.f;
q-》fnode.g=n.g;
q-》fnode.h=n.h;
q-》fnode.x=n.x;
q-》fnode.y=n.y;
q-》fnode.old=n.old;
q-》fnode.sign=n.sign=2;
}
else
q=q-》next;
}
closed-》pri=(link *)malloc(sizeof(link));
closed-》pri-》pri=q;
closed-》pri-》next=closed;
q-》next=closed-》pri;
q=q-》next;
q-》fnode.flag=n.flag;
q-》fnode.f=n.f;
q-》fnode.g=n.g;
q-》fnode.h=n.h;
q-》fnode.x=n.x;
q-》fnode.y=n.y;
q-》fnode.old=n.old;
q-》fnode.sign=n.sign=2;
}
void out_closed(node n)//将n节点从closed表中移出
{
q=closed;
while(q-》next!=closed)
{
if(n.f=q-》fnode.f)
{
link *q1;
q1=q-》next;
q-》next=q-》next-》next;
q-》next-》pri=q;
free(q1);
n.sign=0;
}
else
q=q-》next;
}
}
void in_bestnode(node n)//将n节点设为bestnode节点
{
while(r-》next!=bestnode)
{
if(n.f》=r-》fnode.f)
{
r-》next-》pri=(link *)malloc(sizeof(link));
r-》next-》pri-》pri=r;
r=r-》next;
r-》pri-》next=r;
r-》pri-》pri-》next=r-》pri;
r=r-》pri;
r-》fnode.flag=n.flag;
r-》fnode.f=n.f;
r-》fnode.g=n.g;
r-》fnode.h=n.h;
r-》fnode.x=n.x;
r-》fnode.y=n.y;
r-》fnode.old=n.old;
}
else
r=r-》next;
}
bestnode-》pri=(link *)malloc(sizeof(link));
bestnode-》pri-》pri=r;
bestnode-》pri-》next=bestnode;
r-》next=bestnode-》pri;
r=r-》next;
r-》fnode.flag=n.flag;
r-》fnode.f=n.f;
r-》fnode.g=n.g;
r-》fnode.h=n.h;
r-》fnode.x=n.x;
r-》fnode.y=n.y;
r-》fnode.old=n.old;
}
void out_bestnode(node n)//将n节点的bestnode去掉
{
r=bestnode;
while(r-》next!=bestnode)
{
if(n.f=p-》fnode.f)
{
link *r1;
r1=r-》next;
r-》next=r-》next-》next;
r-》next-》pri=r;
free(r1);
}
else
r=r-》next;
}
}
void in_successor(node n)//将n节点设置为successor节点
{
s=successor;
while(s-》next!=successor)
{
if(n.f》=s-》fnode.f)
{
s-》next-》pri=(link *)malloc(sizeof(link));
s-》next-》pri-》pri=s;
s=p-》next;
s-》pri-》next=s;
s-》pri-》pri-》next=s-》pri;
s=s-》pri;
s-》fnode.flag=n.flag;
s-》fnode.f=n.f;
s-》fnode.g=n.g;
s-》fnode.h=n.h;
s-》fnode.x=n.x;
s-》fnode.y=n.y;
s-》fnode.old=n.old;
}
else
s=s-》next;
}
successor-》pri=(link *)malloc(sizeof(link));
successor-》pri-》pri=s;
successor-》pri-》next=successor;
s-》next=successor-》pri;
s=s-》next;
s-》fnode.flag=n.flag;
s-》fnode.f=n.f;
s-》fnode.g=n.g;
s-》fnode.h=n.h;
s-》fnode.x=n.x;
s-》fnode.y=n.y;
s-》fnode.old=n.old;
}
void out_successor(node n)//将n节点的successor去掉
{
s=successor;
while(s-》next!=successor)
{
if(n.f=p-》fnode.f)
{
link *s1;
s1=s-》next;
s-》next=s-》next-》next;
s-》next-》pri=s;
free(s1);
}
else
s=s-》next;
}
}
void print(link *n)//输出link类型的表n
{
link *forprint;
forprint=n;
printf("the key is ");
while(forprint-》next!=n)
printf("(%d,%d)\n",forprint-》fnode.x,forprint-》fnode.y);
}
int main()
{
//初始化部分
//这部分的功能是将二维的整形数组赋值给node型的二维数组
int i=0,j=0;
for(i=0;i《7;i++)
for(j=0;j《7;j++)
{
maze.x=i;
maze.y=j;
maze;
if(maze.flag==0)
{
maze.h=6-i+6-j;
maze.old=0;
}
else
maze.h=-1;
}
for(i=0;i《7;i++)//输出迷宫示意图
{
for(j=0;j《7;j++)
{
printf("%2d",maze_flag);
}
printf("\n");
}
//这部分的功能是将open,closed,bestnode表初始化,都置为空表
p=open=(link *)malloc(sizeof(link));
open-》next=open;
open-》pri=open;
q=closed=(link *)malloc(sizeof(link));
closed-》next=closed;
closed-》pri=closed;
r=bestnode=(link *)malloc(sizeof(link));
bestnode-》next=bestnode;
bestnode-》pri=bestnode;
//将第一个元素即(0,0)节点放入open表,开始算法
in_open(maze);
maze.h;
link *s2;
s2=successor;
if(open-》next!=open)//open表为空时则失败退出
{
while(1)
{
in_bestnode(open-》fnode);//将open表的第一个元素放入bestnode中
in_closed(maze);//将open表的第一个元素放入closed中
maze.g++;//将open表的第一个元素的g值加一,表示已经走了一步
out_open(maze);//将open表的第一个元素删除
if(bestnode-》fnode.x==6&&bestnode-》fnode.y==6)//若bestnode是目标节点,则成功退出
{
printf("succes!!\nthen print the key:\n");
print(closed);
break;
}
else//若bestnode不是目标节点,则扩展其临近可以走的节点为successor
{
if(i==0||j==0||i==6||j==6)
{
if(i==0&&j==0)//若为(0,0),则判断右边和下边的元素
{
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
}
else if(i==0&&j==6)//若为(0,6),则判断左边和下边的元素
{
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
}
else if(i==6&&j==0)//若为(6,0),则判断左边和上边的元素
{
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
}
else if(i==6&&j==6)//若为(6,6),则判断左边和上边的元素
{
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
}
else if(i==0)//若为第一行的元素(不在角上),则判断左边,下边和右边
{
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
}
else if(i==6)//若为第七行的元素(不在角上),则判断左边,上边和右边
{
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
}
else if(j==0)//若为第一列的元素(不在角上),则判断右边,下边和上边
{
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
}
else if(j==6)//若为第七列的元素(不在角上),则判断左边,上边和上边
{
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
}
}
else//若为中将的元素,则判断四个方向的节点
{
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
if(judge(maze)==0)
in_successor(maze);
}
}
while(s2-》next!=successor)//对所有的successor节点进行下列操作
{
maze.g=bestnode-》fnode.g+bestnode-》fnode.h;//计算g(suc)=g(bes)+h(bes,suc)
if(s2-》fnode.sign==1)//若在open表中,则置为old,记下较小的g,并从open表中移出,放入closed表中
{
s2-》fnode.old=1;
if(s2-》fnode.g《maze.g)
{
maze.g=s2-》fnode.g;
maze.h;
out_open(maze);
in_closed(maze);
maze.old=0;
}
else
continue;
}
else if(s2-》fnode.sign==2)//若在closed表中,则置为old,记下较小的g,并将old从closed表中移出,将较小的g的节点放入closed表中
{
s2-》fnode.old=1;
if(s2-》fnode.g《maze.g)
{
maze.g=s2-》fnode.g;
maze.h;
out_closed(maze);
in_closed(maze);
maze.old=0;
}
else
continue;
}
else//若即不再open表中也不在closed表中,则将此节点放入open表中,并计算此节点的f值
{
in_open(maze);
maze.h;
}
s2=s2-》next;
}
s2=successor;
}
}
else
printf("error!!This maze does not have the answer!");
return(0);
}

迷宫求解

有算法了，代码就很好写了。
请参考以下：
//顺序栈的应用：迷宫
//作者：nuaazdh
//时间：2011年12月7日
#include 《stdio.h》
#include 《stdlib.h》
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define COLUMN 10 //迷宫行数#define ROW 10 //迷宫列数
typedef int Status; //函数返回状态
typedef struct{//迷宫类型
char **maze;//迷宫数据
int **footprint;//足迹数据
int row;//行数
int column;//列数
}MazeType;
typedef struct{//迷宫位置坐标
int x;
int y;
}PosType;
typedef struct{
int ord;//通道块在路劲上的"序号"
PosType seat;//通道块在迷宫中的"坐标位置"
int di;//从此通信块走向下一通道块的"方向"
}SElemType; //栈元素类型
typedef struct{//顺序栈结构定义
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack *S);
//构造一个空栈S
Status InitMaze(MazeType *M);
//初始化迷宫数据
Status DestroyStack(SqStack *S);
//销毁栈S，S不再存在
Status ClearStack(SqStack *S);
//把栈S置为空栈
Status StackEmpty(SqStack S);
//若栈S为空栈，则返回TRUE，否则返回FALSE
int StackLength(SqStack S);
//返回S元素的个数，即栈的长度
Status GetTop(SqStack S,SElemType *e);
//若栈不为空，则用e返回S的栈顶元素，并返回OK；否则返回FALSE
Status Push(SqStack *S,SElemType e);
//插入元素e为新的栈顶元素
Status Pop(SqStack *S,SElemType *e);
//若栈S不为空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR
Status StackTraverse(const SqStack *S);
//从栈底到栈顶依次对每个元素进行访问
Status PrintMaze(MazeType *M);
//输出迷宫
Status MazePath(SqStack *S,MazeType maze,PosType start,PosType end);
//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底
//到栈顶），并返回TRUE；否则返回FALSE
Status FootPrint(MazeType *M,PosType pos);
//将迷宫的当前位置pos设置为"走过"，即footprint该位置为1
Status Pass(MazeType *M,PosType pos);
//判断当前位置是否走过
SElemType NewSElem(int step,PosType pos,int d);
//创建新结点，用step，pos，d初始化该结点
PosType NextPos(PosType pos,int d);
//将位置pos的方向设为d
Status MarkPrint(MazeType *M,PosType pos);
//将迷宫M的pos位置，设为已走，成功返回OK；否则返回ERROR
Status PrintFoot(MazeType *M,SqStack *S);
//输出迷宫的路径
int main()
{
MazeType maze;//迷宫结构
SqStack stack;//顺序栈，存储迷宫路径
PosType start,end;//迷宫的起点和终点；
start.x=0;start.y=1;//迷宫的起点
end.x=8;end.y=9;//迷宫的终点
InitMaze(&maze);//迷宫初始化
printf("迷宫形状：\n");
PrintMaze(&maze);//打印迷宫形状
if(TRUE==MazePath(&stack,maze,start,end))
printf("迷宫可解.\n");
else
printf("迷宫不可解.\n");
return 0;
}
Status InitStack(SqStack *S){
//构造一个空栈S
S-》base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S-》base)//分配失败
{
printf("分配内存失败.\n");
exit(0);
}
S-》top=S-》base;
S-》stacksize=STACK_INIT_SIZE;
return OK;
}
Status InitMaze(MazeType *M){
//初始化迷宫数据
int i,j;
char mz={
’#’,’ ’,’#’,’#’,’#’,’#’,’#’,’#’,’#’,’#’,
’#’,’ ’,’ ’,’#’,’ ’,’ ’,’ ’,’#’,’ ’,’#’,
’#’,’ ’,’ ’,’#’,’ ’,’ ’,’ ’,’#’,’ ’,’#’,
’#’,’ ’,’ ’,’ ’,’ ’,’#’,’#’,’ ’,’ ’,’#’,
’#’,’ ’,’#’,’#’,’#’,’ ’,’ ’,’ ’,’ ’,’#’,
’#’,’ ’,’ ’,’ ’,’#’,’ ’,’#’,’ ’,’#’,’#’,
’#’,’ ’,’#’,’ ’,’ ’,’ ’,’#’,’ ’,’ ’,’#’,
’#’,’ ’,’#’,’#’,’#’,’ ’,’#’,’#’,’ ’,’#’,
’#’,’#’,’ ’,’ ’,’ ’,’ ’,’ ’,’ ’,’ ’,’ ’,
’#’,’#’,’#’,’#’,’#’,’#’,’#’,’#’,’#’,’#’
};
M-》maze=(char **)malloc(sizeof(char *)*ROW);
M-》footprint=(int **)malloc(sizeof(int *)*ROW);
if(!M-》maze||!M-》footprint){
printf("申请空间失败，迷宫无法初始化.\n");
return ERROR;
exit(0);
}
for(i=0;i《ROW;i++){
M-》maze=(char *)malloc(sizeof(char)*COLUMN);
M-》footprint=(int *)malloc(sizeof(int)*COLUMN);
if(!M-》maze){
printf("申请空间失败，迷宫初始化失败.\n");
return ERROR;
exit(0);
}
}
for(i=0;i《ROW;i++){
for(j=0;j《COLUMN;j++){
M-》maze;
M-》footprint=0;
}
}
M-》row=ROW;//行
M-》column=COLUMN;//列
return OK;
}
Status DestroyStack(SqStack *S){
//销毁栈S，S不再存在
if(!S)//S为空
{
printf("指针为空，释放失败.\n");
exit(0);
}
free(S);
return OK;
}
Status ClearStack(SqStack *S){
//把栈S置为空栈
if(!S)//S不存在
return FALSE;
S-》top=S-》base;//直接将栈顶指针指向栈底
return OK;
}
Status StackEmpty(SqStack S){
//若栈S为空栈，则返回TRUE，否则返回FALSE
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
int StackLength(SqStack S){
//返回S元素的个数，即栈的长度
return S.stacksize;
}
Status GetTop(SqStack S,SElemType *e){
//若栈不为空，则用e返回S的栈顶元素，并返回OK；否则返回FALSE
if(S.top==S.base){
printf("栈为空.\n");
return FALSE;
}else{
*e=*(S.top-1);
printf("栈顶元素：%c\n",*e);
return OK;
}
}
Status Push(SqStack *S,SElemType e){
//插入元素e为新的栈顶元素
if(S-》top-S-》base》=S-》stacksize){//栈已满，追加存储空间
S-》base=(SElemType *)realloc(S-》base,(S-》stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S-》base)
{
printf("重新申请空间失败.\n");
exit(0);
}
S-》top=S-》base+S-》stacksize;//更改栈顶指针
S-》stacksize+=STACKINCREMENT;
}
*S-》top++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e){
//若栈S不为空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR
if(S-》top==S-》base){//栈为空
printf("栈为空.\n");
return ERROR;
}
*e=*(--S-》top);
return OK;
}
Status StackTraverse(const SqStack *S){
//从栈底到栈顶依次对每个元素进行访问
SElemType *p=S-》base;
if(S-》base==S-》top)
{
printf("栈为空.\n");
return FALSE;
}
printf("栈中元素：");
while(p!=S-》top)
{
printf("x=%d,y=%d\n",p-》seat.x,p-》seat.y);
*p++;
}
printf("\n");
return OK;
}
Status PrintMaze(MazeType *M){
//输出迷宫
int i,j;
for(i=0;i《M-》row;i++){
for(j=0;j《M-》column;j++){
printf("%c",M-》maze);
}
printf("\n");
}
printf("\n");
return OK;
}
Status PrintFoot(MazeType *M,SqStack *S){
//输出迷宫的路径
int i,j;
SElemType *p;
for(i=0;i《M-》row;i++){
for(j=0;j《M-》column;j++){
M-》footprint=0;
}
}
p=S-》base;
if(S-》base==S-》top)
{
printf("栈为空.\n");
return FALSE;
}
while(p!=S-》top)
{
M-》footprint=1;
*p++;
}
for(i=0;i《M-》row;i++){
for(j=0;j《M-》column;j++){
printf("%d",M-》footprint);
}
printf("\n");
}
return OK;}
Status MazePath(SqStack *S,MazeType maze,PosType start,PosType end){
//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底
//到栈顶），并返回TRUE；否则返回FALSE
int curstep=1;//当前步数
SElemType e;
PosType curpos=start;//当前位置
InitStack(S);//初始化栈
do{
if(TRUE==Pass(&maze,curpos)){
FootPrint(&maze,curpos);
e=NewSElem(curstep,curpos,1);
Push(S,e);
if((curpos.x==end.x)&&(curpos.y==end.y)){//到达终点（出口）
printf("迷宫路径:\n");
//StackTraverse(S);
PrintFoot(&maze,S);
return TRUE;
}
curpos=NextPos(curpos,1);
curstep++;
}//if
else{//当前位置不能通过
if(!StackEmpty(*S)){
Pop(S,&e);
while(e.di==4&&!StackEmpty(*S)){
MarkPrint(&maze,e.seat);
Pop(S,&e);
}//while
if(e.di《4){
e.di++;
Push(S,e);
curpos=NextPos(e.seat,e.di);
}//if
}//if
}//else
//PrintFoot(&maze,S);
}while(!StackEmpty(*S));
return FALSE;
}
Status FootPrint(MazeType *M,PosType pos){
//将迷宫的当前位置pos设置为"走过"，即footprint该位置为1
if((pos.x》M-》row)||(pos.y》M-》column))
return FALSE;
M-》footprint=1;
return TRUE;
}
Status Pass(MazeType *M,PosType pos){
//判断当前位置是否可通，即为走过的通道块
if((M-》row《pos.x)||(M-》column《pos.y)){
printf("位置越位.\n");
exit(0);
}
if((0==M-》footprint==’ ’))
return TRUE;
else
return FALSE;
}
SElemType NewSElem(int step,PosType pos,int d){
//创建新结点，用step，pos，d初始化该结点
SElemType e;
e.ord=step;
e.seat=pos;
e.di=d;
return e;
}
PosType NextPos(PosType pos,int d){
//获取pos位置d方向的位置
switch(d){
case 1://东
pos.x++;
break;
case 2://南
pos.y++;
break;
case 3://西
pos.x--;
break;
case 4://北
pos.y--;
break;
default:
printf("位置编号出错.\n");
}
return pos;
}
Status MarkPrint(MazeType *M,PosType pos){
//将迷宫M的pos位置，设为已走，成功返回OK；否则返回ERROR
if(pos.x》M-》row||pos.y》M-》column){
printf("所要标记位置越位.\n");
return ERROR;
}
M-》footprint=1;
return OK;
}

跪求高手 数据结构迷宫问题

#define N 7 /*地图的第一维长度*/
#include 《iostream.h》
#include 《stdlib.h》
#include"ds.h"
#define O 5
#define P 5
typedef struct
{
int x;/* 行下标 */
int y;/* 列下标 */
int d;/* 运动方向 */
} DataType;
struct StackNode /* 链栈类型定义 */
{
struct StackNode *next;
DataType s;
};
typedef struct StackNode *LinkStack; /* 链栈类型的指针类型 */
int createEmptyStack_seq(LinkStack &S)
{
S=NULL;
return OK;
}
int isEmptyStack_seq( LinkStack pastack )
{
if(pastack==NULL)
return TRUE;
else return FALSE;
}
/* 在栈顶压入一元素x */
void push_seq( LinkStack &pastack, DataType x )
{
LinkStack p;
p = (LinkStack)malloc(sizeof(struct StackNode));
p-》s=x;
p-》next=pastack;
pastack=p;
}
/* 删除栈顶元素 */
void pop_seq( LinkStack &pastack )
{
LinkStack p;
if (!isEmptyStack_seq(pastack) )
{
p=pastack;
pastack=pastack-》next;
free(p);

}
else
{
cout《《"栈已空，没有元素出栈！\n";

}
}
/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
DataType top_seq( LinkStack pastack )
{
if (!isEmptyStack_seq(pastack) )
return (pastack-》s);
}
void pushtostack(LinkStack &st, int x, int y, int d) {
DataType element;
element.x = x;
element.y = y;
element.d = d;
push_seq(st, element);
}
void printpath(LinkStack st)
{
DataType element;
LinkStack S;
createEmptyStack_seq(S );
cout《《"The revers path is:\n"; /* 打印路径上的每一点 */
while(!isEmptyStack_seq(st))
{
element = top_seq(st);
pop_seq(st);
push_seq(S,element);

}
while(!isEmptyStack_seq(S))
{
element = top_seq(S);
pop_seq(S);
cout《《"("《《element.x《《","《《element.y《《","《《element.d+1《《")"《《endl;
}
}
/* 迷宫maze的一条路径 */
/* 其中 1《=x1,x2《=M-2 , 1《=y1,y2《=N-2 */
void mazePath(int maze, int x1, int y1, int x2, int y2)
{
int i, j, k, g, h;
LinkStack st;
DataType element;
createEmptyStack_seq(st );
maze = 2; /* 从入口开始进入,作标记 */
pushtostack(st, x1, y1, -1); /* 入口点进栈 */
while ( !isEmptyStack_seq(st)) /* 走不通时,一步步回退 */
{
element = top_seq(st);
pop_seq(st);
i = element.x; j = element.y;
for (k = element.d + 1; k 《= 3; k++) /* 依次试探每个方向 */
{
g = i + direction;
if (g == x2 && h == y2 && maze == 0) /* 走到出口点 */
{
pushtostack(st, i, j, k);
printpath(st); /* 打印路径 */
return;
}

if (maze == 0) /* 走到没走过的点 */
{
maze = 2; /* 作标记 */
pushtostack(st, i, j, k); /* 进栈 */
i = g; j = h; k = -1; /* 下一点转换成当前点 */
}
}
}
cout《《"The path has not been found.\n";/* 栈退完未找到路径 */
}
int main()
{
int direction={0,1,1,0,0,-1,-1,0};
int i,j;
int a;
cout《《"请用0，1来设置"《《O《《"*"《《P《《"阶的矩阵迷宫"《《endl;
for(i=0;i《O;i++)
{
for(j=0;j《P;j++)
cin》》a;
}
for(i=1;i《=O;i++)
for(j=1;j《=P;j++)
maze;
for(j=0;j《P+2;j++)
maze=1;
for(i=0;i《O+2;i++)
maze=1;
mazePath(maze,direction,1,1,O,P);

return 0;
}
这是我做的，完全符合要求，迷宫大小可以宏定义的时候设定，“ds.h”文件自己加一下就好了啊！

数据结构迷宫问题（c语言）

#include《stdio.h》
#include《string.h》
#include《stdlib.h》
#include《time.h》
int m,n,num,map={0,-1,0,1,-1,0,1,0},ans,flag;
void maze()
{
int i,j;
time_t t;
srand(time(&t));
for(i=0;i《m;i++)
for(j=0;j《n;j++)
{
map=rand()%2;
if(map)
num++;
}
if(num《m*n/2)
{
for(i=0;i《m;i++)
for(j=0;j《n;j++)
if(!map)
map+=rand()%2;
}
map=1;
map=1;
}
void print()
{
int i,j;
for(i=0;i《m;i++)
for(j=0;j《n;j++)
{
printf("%d ",map);
if(j==n-1)puts("");
}
}
void dfs(int x,int y)
{
int i,tx,ty;
if(!flag)
return;
for(i=0;i《4;i++)
{
tx=x+d;
ty=y+d;
if(!f)
{
f=1;
a=tx;
b=ty;
if(tx+ty==0)
{
printf("(%d,%d)\n",m,n);
for(flag=i=0;i《ans;i++)
printf("(%d,%d)\n",a+1);
return;
}
dfs(tx,ty);
f=0;
ans--;
}
}
}
int main()
{
while(scanf("%d%d",&m,&n),m+n)
{
memset(f,0,sizeof(f));
num=ans=0;
flag=1;
maze();
print();
dfs(m-1,n-1);
if(flag)
puts("There is no path");
}
return 0;
}

用数据结构解迷宫

#include 《graphics.h》
#include 《stdlib.h》
#include 《stdio.h》
#include 《conio.h》
#include 《dos.h》
#define N 20/*迷宫的大小，可改变*/
int oldmap;/*递归用的数组,用全局变量节约时间*/
int yes=0;/*yes是判断是否找到路的标志,1找到，0没找到*/
int way,wayn=0;/*way数组是显示路线用的,wayn是统计走了几个格子*/
void Init(void);/*图形初始化*/
void Close(void);/*图形关闭*/
void DrawPeople(int *x,int *y,int n);/*画人工探索物图*/
void PeopleFind(int (*x));/*人工探索*/
void WayCopy(int (*x));/*为了8个方向的递归，把旧迷宫图拷贝给新数组*/
int FindWay(int (*x),int i,int j);/*自动探索函数*/
void MapRand(int (*x));/*随机生成迷宫函数*/
void PrMap(int (*x));/*输出迷宫图函数*/
void Result(void);/*输出结果处理*/
void Find(void);/*成功处理*/
void NotFind(void);/*失败处理*/
void main(void)/*主函数*/
{
int map; /*迷宫数组*/
char ch;
clrscr();
printf("\n Please select hand(1) else auto\n");/*选择探索方式*/
scanf("%c",&ch);
Init(); /*初始化*/
MapRand(map);/*生成迷宫*/
PrMap(map);/*显示迷宫图*/
if(ch==’1’)
PeopleFind(map);/*人工探索*/
else
FindWay(map,1,1);/*系统自动从下标1,1的地方开始探索*/
Result();/*输出结果*/
Close();
}
void Init(void)/*图形初始化*/
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"c:\\tc");
}
void DrawPeople(int *x,int *y,int n)/*画人工控制图*/
{/*如果将以下两句注释掉，则显示人工走过的路径，*/
setfillstyle(SOLID_FILL,WHITE); /*设置白色实体填充样式*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
/*恢复原通路*/
switch(n)/*判断x,y的变化，8个方向的变化*/
{
case 1: (*x)--;break; /*上*/
case 2: (*x)--;(*y)++;break ;/*右上*/
case 3: (*y)++;break; /*右*/
case 4: (*x)++;(*y)++;break; /*右下*/
case 5: (*x)++;break; /*下*/
case 6: (*x)++;(*y)--;break; /*左下*/
case 7: (*y)--;break; /*左*/
case 8: (*x)--;(*y)--;break; /*左上*/
}
setfillstyle(SOLID_FILL,RED);/*新位置显示探索物*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
}
void PeopleFind(int (*map))/*人工手动查找*/
{
int x,y;
char c=0;/*接收按键的变量*/
x=y=1;/*人工查找的初始位置*/
setcolor(11);
line(500,200,550,200);
outtextxy(570,197,"d");
line(500,200,450,200);
outtextxy(430,197,"a");
line(500,200,500,150);
outtextxy(497,130,"w");
line(500,200,500,250);
outtextxy(497,270,"x");
line(500,200,450,150);
outtextxy(445,130,"q");
line(500,200,550,150);
outtextxy(550,130,"e");
line(500,200,450,250);
outtextxy(445,270,"z");
line(500,200,550,250);
outtextxy(550,270,"c");/*以上是画8个方向的控制介绍*/
setcolor(YELLOW);
outtextxy(420,290,"Press ’Enter’ to end");/*压回车键结束*/
setfillstyle(SOLID_FILL,RED);
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/*入口位置显示*/
while(c!=13)/*如果按下的不是回车键*/
{
c=getch();/*接收字符后开始各个方向的探索*/
if(c==’w’&↦!=1)
DrawPeople(&x,&y,1);/*上*/
else
if(c==’e’&↦!=1)
DrawPeople(&x,&y,2);/*右上*/
else
if(c==’d’&↦!=1)
DrawPeople(&x,&y,3);/*右*/
else
if(c==’c’&↦!=1)
DrawPeople(&x,&y,4);/*右下*/
else
if(c==’x’&↦!=1)
DrawPeople(&x,&y,5);/*下*/
else
if(c==’z’&↦!=1)
DrawPeople(&x,&y,6); /*左下*/
else
if(c==’a’&↦!=1)
DrawPeople(&x,&y,7); /*左*/
else if(c==’q’&↦!=1)
DrawPeople(&x,&y,8); /*左上*/
}
setfillstyle(SOLID_FILL,WHITE); /*消去红色探索物，恢复原迷宫图*/
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);
if(x==N-2&&y==N-2)/*人工控制找成功的话*/
yes=1; /*如果成功标志为1*/
}
void WayCopy(int (*oldmap))/*拷贝迷宫数组 */
{
int i,j;
for(i=0;i《N;i++)
for(j=0;j《N;j++)
oldmap;
}
int FindWay(int (*map),int i,int j)/*递归找路*/
{
if(i==N-2&&j==N-2)/*走到出口*/
{
yes=1;/*标志为1,表示成功*/
return;
}
map=1;/*走过的地方变为1*/
WayCopy(oldmap,map); /*拷贝迷宫图*/
if(oldmap==0&&!yes)/*判断右下方是否可走*/
{
FindWay(oldmap,i+1,j+1);
if(yes)/*如果到达出口了，再把值赋给显示路线的way数组,也正是这个原因,所以具体路线是从最后开始保存*/
{
way=i;
way=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap==0&&!yes)/*判断下方是否可以走,如果标志yes已经是1也不用找下去了*/
{
FindWay(oldmap,i+1,j);
if(yes)
{
way=i;
way=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap==0&&!yes)/*判断右方是否可以走*/
{
FindWay(oldmap,i,j+1);
if(yes)
{
way=i;
way=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap==0&&!yes)/*判断上方是否可以走*/
{
FindWay(oldmap,i-1,j);
if(yes)
{
way=i;
way=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap==0&&!yes)/*判断右上方是否可以走*/
{
FindWay(oldmap,i-1,j+1);
if(yes)
{
way=i;
way=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap==0&&!yes)/*判断左下方是否可以走*/
{
FindWay(oldmap,i+1,j-1);
if(yes)
{
way=i;
way=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap==0&&!yes)/*判断左方是否可以走*/
{
FindWay(oldmap,i,j-1);
if(yes)
{
way=i;
way=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap==0&&!yes)/*判断左上方是否可以走*/
{
FindWay(oldmap,i-1,j-1);
if(yes)
{
way=i;
way=j;
return;
}
}
return;
}
void MapRand(int (*map))/*开始的随机迷宫图*/
{
int i,j;
cleardevice();/*清屏*/
randomize(); /*随机数发生器*/
for(i=0;i《N;i++)
{
for(j=0;j《N;j++)
{
if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈为墙壁*/
map=1;
else
if(i==1&&j==1||i==N-2&&j==N-2)/*出发点与终点表示为可走的*/
map=0;
else
map=random(2);/*其它的随机生成0或1*/
}
}
}
void PrMap(int (*map))/*输出迷宫图*/
{
int i,j;
for(i=0;i《N;i++)
for(j=0;j《N;j++)
if(map==0)
{
setfillstyle(SOLID_FILL,WHITE);/*白色为可走的路*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
else
{
setfillstyle(SOLID_FILL,BLUE);/*蓝色为墙壁*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
}
void Find(void)/*找到通路*/
{
int i;
setfillstyle(SOLID_FILL,RED);/*红色输出走的具体路线*/
wayn--;
for(i=wayn;i》=0;i--)
{
bar(100+way*15-6,100+
way*15+6);
sleep(1);/*控制显示时间*/
}
bar(100+(N-2)*15-6,50+(N-2)*15-6,100+
(N-2)*15+6,50+(N-2)*15+6); /*在目标点标红色*/
setcolor(GREEN);
settextstyle(0,0,2);/*设置字体大小*/
outtextxy(130,400,"Find a way!");
}
void NotFind(void)/*没找到通路*/
{
setcolor(GREEN);
settextstyle(0,0,2);/*设置字体大小*/
outtextxy(130,400,"Not find a way!");
}
void Result(void)/*结果处理*/
{
if(yes)/*如果找到*/
Find();
else/*没找到路*/
NotFind();
getch();
}
void Close(void)/*图形关闭*/
{
closegraph();
}
 另外一个，是数据结构的：
#include《stdio.h》
#define NUM 10/* 定义物品总数*/
#define CONTENT 10 /*定义包的容量*/
void knapsack(int v)
{
int n=NUM-1;
int i,j;
int jMax;
if((w-1)《 c)
jMax = w-1;
else
jMax = c;
/* 初始化m */
for(j = 0; j 《= jMax; j++)
m = 0;
for(j = jMax +1; j 《= c; j++)
m;
/*使用非递归的算法来求解m */
for(i = n-1; i 》 0; i--)
{
if((w-1)《 c)
jMax = w-1;
else
jMax = c;
for(j = 0; j 《= jMax; j++)
m ;
for(j = jMax +1; j 《= c; j++)
{
if(m))
m ;
else
m;
}
}
if(c》w)
{
if(m))
m;
else
m;
}
else
m;

}
/*寻找最优解*/
void traceback(int flag)
{
int n = NUM -1;
int i;
int c = CONTENT;
for(i = 0; i 《 n; i++)
{
if(m)
flag = 0;
else
{
flag = 1;
c-=w;
}
}
if(m 》0)
flag = 1;
else
flag = 0;
}
/* 打印最优解*/
void printResult(int flag)
{
int i;
printf("the knapsack should contain:\n");
printf(" num weight value \n");
for(i = 0;i 《 NUM; i++)
{
if(flag == 1)
printf(" %d %d %d\n",i,w);
}
printf("the max value in the knapsack is: %d\n",m);
}
int main()
{
int value={5,2,3,4,3,6,5,7,8,2};
int weight={2,1,3,2,4,3,5,6,2,2};
int c = CONTENT;
int maxvalue;
int flag={0,0,0,0,0,0,0,0,0,0};
clrscr();
printf("****************************************\n");
printf("* this program will solve *\n");
printf("* the problem of 0-1knapsack *\n");
printf("****************************************\n");
/*计算最优值*/
knapsack(value,weight,c,maxvalue);
/*构造最优解*/
traceback(flag,weight,maxvalue);
/*打印程序的结果*/
printResult(flag,weight,value,maxvalue);
getch();
return 0;
}

迷宫问题，C语言

#include《stdio.h》
int main(void)
{
int maze;
int MAZE;
int m,n;
int p,q;
printf("输入迷宫的行数m,列数n:\n");
scanf("%d%d",&m,&n);
for(p=0;p《=n+1;p++){
maze=1;
maze=1;
}
for(p=1;p《=m;p++){
maze=1;
maze=1;
printf("输入第%d行迷宫:\n",p);
for(q=1;q《=n;q++){
scanf("%d",&maze);
MAZE;
}
}
struct location{
int row;
int col;
}way;
int movehoriz={-1,0,1,1,1,0,-1,-1};
int movevert={1,1,1,0,-1,-1,-1,0};
int endrow=m;
int endcol=n;
way.row=1;
way.col=1;
int start=3;
int i=0;
int k;
int j;
int found=0;
while(!found){
for(k=start;k《start+8;k++){
if((maze.col)))){
way;
way;
i++;
start=(k+5)%8;
break;
}
if((way.col==endcol)){
break;
}
if((maze.col)){
way.row=0;
way.col=0;
maze=1;
i--;
start=(start+4)%8;
}
}
if(k》=start+8){
break;
}
if((way.col==endcol)){
found=1;
break;
}

}
if(found){
for(j=0;j《=i;j++){
printf("maze.col);
}
}
else{
printf("The maze does not have a path\n");
}

}
QQ：366597114 不一定完全对。也许有小错误。有问题可以来问我哈

数据结构C语言版的迷宫问题如何解决

#include"iostream.h"
#include"stdlib.h"
#include"stdio.h"
#define M 10
#define N 10
struct mark //定义迷宫内点的坐标类型
{
int x;
int y;
};
struct Element //栈元素
{
int x,y; //x行,y列
int d; //d下一步的方向
};
typedef struct LStack //链栈
{
Element elem;
struct LStack *next;
}*PLStack;
int InitStack(PLStack &S)
{//构造空栈
S=NULL;
return 1;
}
int StackEmpty(PLStack S)
{//判断栈是否为空
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)
{//压入新数据元素
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p-》elem=e;
p-》next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e)
{//栈顶元素出栈
PLStack p;
if(!StackEmpty(S))
{
e=S-》elem;
p=S;
S=S-》next;
free(p);
return 1;
}
else
return 0;
}
void MazePath(struct mark start,struct mark end,int maze)
{//求迷宫路径函数
int i,j,d;
int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze=2; //入口点作上标记
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //开始为-1
Push(S1,elem);
while(!StackEmpty(S1)) //栈不为空 有路径可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一个方向
while(d《4) //试探东南西北各个方向
{
a=i+diradd;
b=j+diradd;
if(a==end.x && b==end.y && maze==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=4; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("0=东 1=南 2=西 3=北 4为则走出迷宫\n通路为:(行坐标,列坐标,方向)\n");
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("--》(%d,%d,%d)",e.x,e.y,e.d);
}
printf("成功 !\n");
return;
}
if(maze==0) //找到可以前进的非出口的点
{
maze=2; //标记走过此点
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //当前位置入栈
i=a; //下一点转化为当前点
j=b; d=-1;
}
d++;
}
}
printf("没有找到可以走出此迷宫的路径,等着憋死吧!\n");
}
void initmaze(int maze)
{//建立迷宫
int i,j;
int m,n; //迷宫行,列
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("请输入迷宫的各行各列:(用空格隔开,0代表路,1代表墙)\n",m,n);
for(i=1;i《=m;i++)
for(j=1;j《=n;j++)
scanf("%d",&maze);
printf("你建立的迷宫为\n");
for(i=0;i《=m+1;i++) //加一圈围墙
{
maze=1;
maze=1;
}
for(j=0;j《=n+1;j++)
{
maze=1;
maze=1;
}
for(i=0;i《=m+1;i++) //输出迷宫
{
for(j=0;j《=n+1;j++)
printf("%d ",maze);
printf("\n");
}
}
void main()
{
int sto;
struct mark start,end; //start,end入口和出口的坐标
int add={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北
initmaze(sto);//建立迷宫
printf("输入入口的横坐标,纵坐标\n");
scanf("%d,%d",&start.x,&start.y);
printf("输入出口的横坐标,纵坐标\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //寻找路径
}

寻求计算机专业编程：1迷宫问题的求解，要求生成迷宫矩阵，求出迷宫最短的通路（数据结构原代码）

#include《iostream》
using namespace std;
class T //定义描述迷宫中当前位置的结构类型
{
public:
int x; //x代表当前位置的行坐标
int y; //y代表当前位置的列坐标
int dir; //0:无效,1:东,2:南,3:西,4:北
};
class LinkNode //链表结点
{
friend class Stack;
public:
T data;
LinkNode *next;
};
class Stack
{
private:
LinkNode *top; //指向第一个结点的栈顶指针
public:
Stack(); //构造函数，置空栈
~Stack(); //析构函数
void Push(T e); //把元素data压入栈中
T Pop(); //使栈顶元素出栈
T GetPop(); //取出栈顶元素
void Clear(); //把栈清空
bool empty(); //判断栈是否为空，如果为空则返回1，否则返回0
};
Stack::Stack() //构造函数，置空栈
{
top=NULL;
}
Stack::~Stack() //析构函数
{
}
void Stack::Push(T e) //把元素x压入栈中
{
LinkNode *P;
P=new LinkNode;
P-》data=e;
P-》next=top;
top=P;
}
T Stack::Pop() //使栈顶元素出栈
{
T Temp;
LinkNode *P;
P=top;
top=top-》next;
Temp=P-》data;
delete P;
return Temp;
}
T Stack::GetPop() //取出栈顶元素
{
return top-》data;
}
void Stack::Clear() //把栈清空
{
top=NULL;
}
bool Stack::empty() //判断栈是否为空，如果为空则返回1，否则返回0
{
if(top==NULL) return 1;
else return 0;
}
int move={{0,1},{1,0},{0,-1},{-1,0}}; //定义当前位置移动的4个方向
bool Mazepath(int **maze,int m,int n);
//寻找迷宫maze中从（0，0）到（m,n）的路径
//到则返回true,否则返回false
void PrintPath(Stack p); //输出迷宫的路径
void Restore(int **maze,int m,int n); //恢复迷宫
int** GetMaze(int &m,int &n); //获取迷宫
//返回存取迷宫的二维指针
int main()
{
int m=0,n=0; //定义迷宫的长和宽
int **maze; //定义二维指针存取迷宫
maze=GetMaze(m,n); //调用GetMaze(int &m,int &n)函数，得到迷宫
if(Mazepath(maze,m,n)) //调用Mazepath(int **maze,int m,int n)函数获取路径
cout《《"迷宫路径探索成功!\n";
else cout《《"路径不存在!\n";
return 0;
}
int** GetMaze(int &m,int &n)//返回存取迷宫的二维指针
{
int **maze; //定义二维指针存取迷宫
int i=0,j=0;
cout《《"请输入迷宫的长和宽:";
int a,b;cin》》a》》b; //输入迷宫的长和宽
cout《《"请输入迷宫内容:\n";
m=a;
n=b; //m,n分别代表迷宫的行数和列数
maze=new int *; //申请长度等于行数加2的二级指针
for(i= 0;i《m+2;i++) //申请每个二维指针的空间
{
maze;
}
for(i=1;i《=m;i++) //输入迷宫的内容，0代表可通，1代表不通
for(j=1;j《=n;j++)
cin》》maze;
for(i=0;i《m+2;i++)
maze=1;
for(i=0;i《n+2;i++)
maze=1;
return maze; //返回存贮迷宫的二维指针maze
};
bool Mazepath(int **maze,int m,int n)//寻找迷宫maze中从（0，0）到（m,n）的路径
//到则返回true,否则返回false
{
Stack q,p; //定义栈p、q,分别存探索迷宫的过程和存储路径
T Temp1,Temp2;
int x,y,loop;
Temp1.x=1;
Temp1.y=1;
q.Push(Temp1); //将入口位置入栈
p.Push(Temp1);
maze=-1; //标志入口位置已到达过
while(!q.empty()) //栈q非空，则反复探索
{
Temp2=q.GetPop(); //获取栈顶元素
if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y))
p.Push(Temp2);
//如果有新位置入栈，则把上一个探索的位置存入栈p
for(loop=0;loop《4;loop++) //探索当前位置的4个相邻位置
{
x=Temp2.x+move; //计算出新位置x位置值
y=Temp2.y+move; //计算出新位置y位置值
if(maze==0) //判断新位置是否可达
{
Temp1.x=x;
Temp1.y=y;
maze=-1; //标志新位置已到达过
q.Push(Temp1); //新位置入栈
}
if((x==(m))&&(y==(n))) //成功到达出口
{
Temp1.x=m;
Temp1.y=n;
Temp1.dir=0;
p.Push(Temp1); //把最后一个位置入栈
PrintPath(p); //输出路径
Restore(maze,m,n); //恢复路径
return 1; //表示成功找到路径
}
}
if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)
//如果没有新位置入栈，则返回到上一个位置
{
p.Pop();
q.Pop();
}
}
return 0; //表示查找失败，即迷宫无路经
}
void PrintPath(Stack p) //输出路径
{
cout《《"迷宫的路径为\n";
cout《《"括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)\n";
Stack t; //定义一个栈，按从入口到出口存取路径
int a,b;
T data;
LinkNode *temp;
temp=new LinkNode; //申请空间
temp-》data=p.Pop(); //取栈p的顶点元素，即第一个位置
t.Push(temp-》data); //第一个位置入栈t
delete temp; //释放空间
while(!p.empty()) //栈p非空，则反复转移
{
temp=new LinkNode;
temp-》data=p.Pop(); //获取下一个位置
//得到行走方向
a=t.GetPop().x-temp-》data.x; //行坐标方向
b=t.GetPop().y-temp-》data.y; //列坐标方向
if(a==1) temp-》data.dir=1; //方向向下，用1表示
else if(b==1) temp-》data.dir=2; //方向向右，用2表示
else if(a==-1) temp-》data.dir=3; //方向向上，用3表示
else if(b==-1) temp-》data.dir=4; //方向向左，用4表示
t.Push(temp-》data); //把新位置入栈
delete temp;
}
//输出路径，包括行坐标，列坐标，下一个位置方向
while(!t.empty()) //栈非空，继续输出
{
data=t.Pop();
cout《《’(’《《data.x《《’,’《《data.y《《’,’《《data.dir《《","; //输出行坐标，列坐标
switch(data.dir) //输出相应的方向
{
case 1:cout《《"↓)\n";break;
case 2:cout《《"→)\n";break;
case 3:cout《《"↑)\n";break;
case 4:cout《《"←)\n";break;
case 0:cout《《")\n";break;
}
}
}
void Restore(int **maze,int m,int n) //恢复迷宫
{
int i,j;
for(i=0;i《m+2;i++) //遍历指针
for(j=0;j《n+2;j++)
{
if(maze==-1) //恢复探索过位置，即把-1恢复为0
maze=0;
}
}
示例输出：
测试1：
请输入迷宫的长和宽:5 5
请输入迷宫内容:
0 1 1 0 0
0 0 1 1 0
1 0 0 1 1
1 0 0 1 0
1 1 0 0 0
迷宫的路径为
括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)
(1,1,1,↓)
(2,1,2,→)
(2,2,1,↓)
(3,2,1,↓)
(4,2,2,→)
(4,3,1,↓)
(5,3,2,→)
(5,4,2,→)
(5,5,0,)
迷宫路径探索成功!
测试2：
请输入迷宫的长和宽:9 8
请输入迷宫内容:
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
迷宫的路径为
括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)
(1,1,1,↓)
(2,1,1,↓)
(3,1,1,↓)
(4,1,1,↓)
(5,1,2,→)
(5,2,2,→)
(5,3,1,↓)
(6,3,2,→)
(6,4,2,→)
(6,5,3,↑)
(5,5,2,→)
(5,6,2,→)
(5,7,1,↓)
(6,7,1,↓)
(7,7,1,↓)
(8,7,1,↓)
(9,7,2,→)
(9,8,0,)
迷宫路径探索成功!