⑴ 迷宫算法（递归和非递归）
去csdn找下，csdn的博客也可以找，下载那可以找相关资料找找
网~站：www.csdn.net
下载：download.csdn.net 注册个账号就能下载
博客：blog.csdn.net
⑵ 一个用栈实现的二维迷宫求通路的递归程序，求大神看看
#include<iostream>
usingnamespacestd;
structNode//节点定义
{
intx;
inty;
Node*next;
Node*front;
};
structStack//栈定义
{
Node*base;
Node*top;
intlength;
};
voidinitStack(Stack&S)//初始化栈
{
S.base=newNode;
S.top=S.base;
S.base->front=NULL;
S.base->next=NULL;
S.length=0;
}
voidPush(Stack&S,intx,inty)
{
Node*p;
p=S.top;
S.top->next=newNode;
S.top=S.top->next;
S.top->front=p;
S.top->x=x;
S.top->y=y;
S.top->next=NULL;
S.length++;
}
voidPop(Stack&S,int&x,int&y)
{
if(S.top->front!=NULL)//栈空
{
Node*p;
p=S.top;
x=S.top->x;
y=S.top->y;
S.top=S.top->front;
S.top->next=NULL;
deletep;
S.length--;
}
}
//引用
voidshow(Stack&S)//显示栈
{
inti,j;
while(S.top->front!=NULL)
{
Pop(S,i,j);
cout<<"("<<i<<","<<j<<")"<<" ";
}
cout<<endl;
}
//引用
intfind(constStack&S,intx,inty)//判断某XY是否在栈中
{
Node*p;
for(p=S.base;p->next!=NULL;p=p->next)
{
if(p->x==x&&p->y==y)return1;
}
return0;
}
//引用
intMaze(int**a,inti,intj,Stack&Path,intn)//迷宫求通路递归算法
{
intc,d;
if(find(Path,i,j))return0;
if(a[i][j]==0)
{
Push(Path,i,j);
if(i==n-1&&j==n-1)return1;
if(Maze(a,i,j+1,Path,n)||Maze(a,i+1,j,Path,n)||Maze(a,i,j-1,Path,n)||Maze(a,i-1,j,Path,n))return1;
else
{
Pop(Path,c,d);
return0;
}
}
elsereturn0;
}
voidinitMaze(intn,int**&a)//动态申请二维数组，形成迷宫
{
inti,j;
a=newint*[n];//申请行空间
for(i=0;i<n;i++)//申请列空间
{
a[i]=newint[n];
}
cout<<"请顺序输入"<<n<<"阶迷宫中每个位置的可行性(0为可行，1为阻断)以回车结束"<<endl;
for(i=0;i<n;i++)//赋值
{
for(j=0;j<n;j++)
{
cin>>a[i][j];
}
}
cout<<"迷宫初始化完成!以下为迷宫："<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
intmain()
{
intn,**a;
StackPath;
initStack(Path);
cout<<"请输入迷宫的阶数n：";
cin>>n;
initMaze(n,a);
switch(Maze(a,0,0,Path,n))
{
case1:
{
cout<<"寻路成功！";
show(Path);//这里的show根本没有显示出来，经过测试可能是Path中根本没有值！！
};break;
case0:cout<<"寻路失败！";break;
}
return0;
}
⑶ 用递归求解迷宫问题
b[9][9] = {....};
a[81][81] = {};
f(i=1,j=1,k=0){
if(i<0 || j<0 ||i>9 ||j>9){
return ;
}
if(i == 8 && j==8){
echo a;
return;
}
if(b[i][j] == 0){
return;
}
a[k][0]=i;
a[k][1]=j;
f(i+1,j,k+1);//往右的结果
a[k][0]=i;
a[k][1]=j;
f(i,j+1,k+1);//往下的结果
a[k][0]=i;
a[k][1]=j;
f(i-1,j,k+1);//往上的结果
a[k][0]=i;
a[k][1]=j;
f(i,j-1,k+1);//往左的结果
}
如果你思路不明白可以再问，哈
⑷ 求解c语言一递归迷宫问题
给你给伪算法：（设坐标为x,y,坐标向右和下延生。）
函数：
｛
判断当前是不是（7,7)，如果是，表示走出迷宫。打印轨迹
1 尝试往左先走一步（x-1，如果x小于0，或者对应位置标识为阻塞）
2 1如果成功，用本函数递归调用左走一步的坐标，并记下当前位置到轨迹列表。
3 尝试往前先走一步（y+1，如果y小于0，或者对应位置标识为阻塞）
4 3如果成功，用本函数递归调用前走一步的坐标,并记下当前位置到轨迹列表。
5 尝试往右先走一步（x+1，如果x小于0，或者对应位置标识为阻塞）
6 5如果成功，用本函数递归调用前走一步的坐标,并记下当前位置到轨迹列表。
如果是（0，0），表示没有合适的路径可走出迷宫。
如果不是（0，0），将轨迹列表最后一位弹出。
｝
⑸ 求解迷宫的递归算法
#include<stdio.h>
#include<malloc.h>
#define M 10
#define N 10
struct node
{
int flag;
int x,y;
};
struct link
{
struct node lnode;
struct link *next;
struct link *pri;
};
struct link *head;
struct node maze[M][N];
int maze_flag[M][N]={{1,1,1,1,1,1,1,1,1,1},
{1,1,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
int judge(int i,int j);
void in_link(struct node nmaze);
void out_link();
void out_put();
void main()
{
int i,j;
head=(struct link *)malloc(sizeof(struct link));
head->next=head;
head->pri=head;
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
maze[i][j].x=i;
maze[i][j].y=j;
maze[i][j].flag=maze_flag[i][j];
}
}
printf("the maze is:\n");
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
printf("%2d",maze_flag[i][j]);
}
printf("\n");
}
head->next=(struct link *)malloc(sizeof(struct link));
head->pri=head->next;
head->next->pri=head;
head->next->next=head;
head->next->lnode.x=1;
head->next->lnode.y=1;
head->next->lnode.flag=1;
printf("wether to find the way?\n");
if(judge(1,1)==1)
printf("the end!\n");
}
int judge(int i,int j)
{
struct node (*pmaze)[N]=maze;
if(pmaze[i][j+1].flag==0)
{
j++;
if((pmaze[i][j].x==M-2)&&(pmaze[i][j].y==N-2))
{
printf("success to find the way!\n");
out_put();
return(1);
}
pmaze[i][j].flag=1;
in_link(pmaze[i][j]);
printf("goin to judge\n");
return(judge(i,j));
}
else
{
if(pmaze[i+1][j].flag==0)
{
i++;
if((pmaze[i][j].x==M-2)&&(pmaze[i][j].y==N-2))
{
printf("success to find the way!\n");
out_put();
return(1);
}
pmaze[i][j].flag=1;
in_link(pmaze[i][j]);
return(judge(i,j));
}
else
{
if(pmaze[i][j-1].flag==0)
{
j--;
if((pmaze[i][j].x==M-2)&&(pmaze[i][j].y==N-2))
{
printf("success to find the way!\n");
out_put();
return(1);
}
pmaze[i][j].flag=1;
in_link(pmaze[i][j]);
return(judge(i,j));
}
else
{
if(pmaze[i-1][j].flag==0)
{
i--;
if((pmaze[i][j].x==M-2)&&(pmaze[i][j].y==N-2))
{
printf("success to find the way!\n");
out_put();
return(1);
}
pmaze[i][j].flag=1;
in_link(pmaze[i][j]);
return(judge(i,j));
}
else
{
out_link();
struct link *q;
q=head;
while(q->next!=head)
{
q=q->next;
}
judge(q->lnode.x,q->lnode.y);
}
}
}
}
}
void in_link(struct node nmaze)
{
struct link *p;
p=head;
while(p->next!=head)
{
p=p->next;
}
p->next=(struct link *)malloc(sizeof(struct link));
p->next->pri=p;
head->pri=p->next;
p->next->next=head;
p=p->next;
p->lnode.x=nmaze.x;
p->lnode.y=nmaze.y;
p->lnode.flag=nmaze.flag;
}
void out_link()
{
struct link *p;
p=head;
while(p->next!=head)
{
p=p->next;
}
p->pri->next=p->next;
head->pri=p->pri;
free(p);
}
void out_put()
{
struct link *r;
r=head;
while(r->next!=NULL)
{
r=r->next;
printf("%2d%2d\n",r->lnode.x,r->lnode.y);
}
printf("%d%d\n",r->lnode.x,r->lnode.y);
}
⑹ 求一个求从迷宫的一点到另一点的最短路径的递归算法
typedef struct node
{
int i;
struct node **nearby;//相邻结点可以有多个，所以这里用指针的指针
} MAPNODE;
MAPNODE a,b;
int minpath(a,b)//从a结点到b结点可以分成两步，1.从a到b的相邻结点。2.从相邻结点到b结点，这就是一个递归的过程
{
int dis=0;
int min=999999;//一个足够大的数据
MAPNODE **p;
if(a.i==b.i)//序号相同表示是同一结点，path为0
{
dis=0;
}
else
{
for(p=b.nearby;*p!=0;p++)
{
dis=0;
dis+=minpath(a,*p);
dis<min?min=dis:;
}
}
return dis;
}
⑺ 用递归算法找出迷宫中所有可行的路径
回溯啊、、、
int ans[1000][2],t=0； //ans数组里存的是每一步的解
void dfs(int x,int y)
{
if (x==x0&&y==y0) {print();return ;} //x0 y0是出口坐标 print（）是输出一个合法解的函数 这个很 简单你自己写吧
然后是枚举下一步可以到达的点 因为我不知道走的规则所以写不出来 只能先假设xx yy是x、y能到达的一个点吧 你可以用for循环枚举能到的点
for (xx.....)
for (yy....)
if (xx,yy满足条件）
{
t++;
ans[t][0]=xx;
ans[t][1]=yy;
dfs(xx,yy)
t--;
}
}
⑻ 数据结构算法（c语言） 迷宫求解
注释非常详细，希望对你有所帮助。
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
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[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=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[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\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);
}
return; //跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴
}
if(maze[a][b]==0) //找到可以前进的非出口的点
{
maze[a][b]=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[M][N])
{
int i,j;
int m,n; //迷宫行,列 [/M]
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宫为(最外圈为墙)...\n");
for(i=0;i<=m+1;i++) //加一圈围墙
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐标
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北 [/M]
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); //find path
system("PAUSE");
}
测试数据，算法复杂度你就自己来写吧，如果你连这都不自己做，那你一定是在应付作业。劝你还是自己运行测试一下吧，免得答辩时老师问你，什么都不知道，那你就悲剧了。祝你好运！！
⑼ 迷宫求解的非递归算法
迷宫求解
任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；
在资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
拜托高手大家些们，我写了个C语言的，但连接编译后才发现25个错误！但我就是找不出来了！麻烦哪位高手给我指点指点！我会追加分的！
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#define N 20
int aa[N][N];
int yes=0;
int x[100][2],n=0;
void fun1(int (*aa)[N],int (*a)[N]);
int fun(int (*a)[N],int i,int j);
void begain(int (*t)[N]);
void pr(int (*t)[N],int nn);
void win(int (*t)[N]);
void lose();
void main(void)
{
int t[N][N];
begain(t);
pr(t,0);
fun(t,1,1);
if(yes)
win(t);
else
lose();
getch();
}
void fun1(int (*aa)[N],int (*a)[N])
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
aa[i][j]=a[i][j];
}
int fun(int (*a)[N],int i,int j)
{
if(i==N-2&&j==N-2)
{
yes=1;
return;
}
a[i][j]=1;
fun1(aa,a);
if(aa[i+1][j+1]==0&&!yes)
{
fun(aa,i+1,j+1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i+1][j]==0&&!yes)
{
fun(aa,i+1,j);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i][j+1]==0&&!yes)
{
fun(aa,i,j+1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i-1][j]==0&&!yes)
{
fun(aa,i-1,j);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i-1][j+1]==0&&!yes)
{
fun(aa,i-1,j+1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i+1][j-1]==0&&!yes)
{
fun(aa,i+1,j-1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i][j-1]==0&&!yes)
{
fun(aa,i,j-1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i-1][j-1]==0&&!yes)
{
fun(aa,i-1,j-1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
}
void begain(int (*t)[N])
{
int i,j;
system(cls);
randomize();
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(i==0||i==N-1||j==0||j==N-1)
t[i][j]=1;
else if(i==1&&j==1||i==N-2&&j==N-2)
t[i][j]=0;
else
t[i][j]=random(2);
}
}
}
void pr(int (*t)[N],int nn)
{
int i,j,ii;
textcolor(RED);
gotoxy(1,1);
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(nn!=1)
printf(%2d,t[i][j]);
else
{
for(ii=0;ii<n;ii++)
{
if(x[ii][0]==i&&x[ii][1]==j)
{
cprintf(%2d,t[i][j]);
break;
}
}
if(ii<n)
continue;
if(i==N-2&&j==N-2)
cprintf( 0);
else
printf(%2d,t[i][j]);
}
}
printf(\n);
}
}
void win(int (*t)[N])
{
int i,j,ii,jj;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(x[j][0]==x[i][0]&&x[j][1]==x[i][1])
{
for(jj=j,ii=i;jj<n;jj++,ii++)
{x[ii][0]=x[jj][0];x[ii][1]=x[jj][1];}
n=n-(j-i);
}
printf(\nThe way is:\n);
for(i=n-1;i>=0;i--)
printf(%3d%3d->,x[i][0],x[i][1]);
printf(%3d%3d\n,N-2,N-2);
t[1][1]=0;
pr(t,1);
}
void lose()
{
printf(\nNot find way!\n);
}