迷宮求解演算法遞歸

⑴ 迷宮演算法（遞歸和非遞歸）

去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);
}