走迷宮演算法題
⑴ 求廣度優先演算法C++走迷宮程序，可以顯示路徑
一般迷宮尋路可以用遞歸的演算法，或者用先進後出的棧數據結構實現
用的是深度優先的演算法，可以尋找到走出迷宮的路徑
但本題要求求出最短的路徑，這就要使用廣度優先的演算法
一般在程序中需要用到先進先出的隊列數據結構
下面是程序的代碼，主要原理是用到
quei，quej和prep三個數組來構成隊列
分別儲存路徑的行，列坐標和上一個節點在隊列中的位置
大致演算法如下，右三個嵌套的循環實現
首先是第一個節點進入隊列
當隊列不空（循環1）
｛
遍歷隊列中每節點(循環2）
｛
將八個方向能夠走的節點加入隊列（循環3）
｝
舊的節點出列
｝
#include<iostream>
#include<ctime>
usingnamespacestd;
#defineMAXNUM50
voidmain()
{
intm,n,i,j,x;
cout<<"請輸入迷宮大小"<<endl;
cin>>m>>n;
intmaze[MAXNUM][MAXNUM];
srand((int)time(NULL));
for(i=0;i<=m+1;i++){
for(j=0;j<=n+1;j++){
if(i==0||j==0||i==m+1||j==n+1)
maze[i][j]=1;
else
{
x=rand()%1000;
if(x>700){maze[i][j]=1;}//控制矩陣中1的個數，太多1迷宮很容易走不通
else{maze[i][j]=0;}
}
cout<<maze[i][j]<<'';
}
cout<<endl;
}
//以上是輸入和迷宮生成，一下是走迷宮
intmove[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
int*quei=newint[m*n];//儲存行坐標隊列
int*quej=newint[m*n];//儲存列坐標隊列
int*prep=newint[m*n];//儲存之前一步在隊列中的位置
inthead,rear,length;//隊列頭，隊列尾，隊列長度
head=0;rear=1;length=1;
quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置進隊列
intpos;//當前節點在隊列中的位置，
intii,jj,ni,nj;//當前節點的坐標，新節點的坐標
intdir;//移動方向
if(maze[1][1]==1)length=0;//第一點就不能通過
elsemaze[1][1]=1;
while(length)//隊列非空繼續
{
for(pos=head;pos<head+length;pos++)//尋找這一層所有節點
{
ii=quei[pos];jj=quej[pos];//當前位置坐標
if(ii==m&&jj==n)break;
for(dir=0;dir<8;dir++)//尋找8個方向
{
ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐標
if(maze[ni][nj]==0)//如果沒有走過
{
quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新節點入隊
rear=rear+1;
maze[ni][nj]=1;//標記已經走過
}
}
}
if(ii==m&&jj==n)break;
head=head+length;
length=rear-head;//這一層節點出列
}
if(ii==m&&jj==n)
{
while(pos!=-1)
{
cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
pos=prep[pos];
if(pos!=-1)cout<<',';
}
}
else
{
cout<<"THEREISNOPATH."<<endl;
}
delete[]quei;
delete[]quej;
delete[]prep;
}
⑵ 設計演算法、編寫程序找出由右上角的門進入，由左下角的門離開以下迷宮的路徑
//走迷宮
//迷宮的布局可能與你的原圖有差異，自己可以修改布局，但不要改迷宮的大小尺寸
//程序僅僅是找出一條可通行的路徑，沒有作找最優路徑的選擇。
#include<stdio.h>
inta[20][20];//記錄迷宮的布局
intff[4][2]={1,0,-1,0,0,1,0,-1};//行走迷宮的四個方向
intplace[360][2];//記錄走的步數
intfx=2,fy=19,tx=18,ty=1;//設置起點(2,19),終點(18,1)
intissame(intn){
inti;
for(i=0;i<n;i++)
if(place[n][0]==place[i][0]&&place[n][1]==place[i][1])
return1;
return0;
}
intnextstep(intn){//迷宮下一步行走
inti,k;
for(i=0;i<4;i++){
place[n][0]=place[n-1][0]+ff[i][0];
place[n][1]=place[n-1][1]+ff[i][1];
if(place[n][0]>19||place[n][0]<1)continue;//行越界
if(place[n][1]>19||place[n][1]<1)continue;//列越界
if(a[place[n][0]][place[n][1]]!=1)continue;//不是1
if(place[n][0]==tx&&place[n][1]==ty)returnn;//到終點
if(issame(n)==1)continue;//走老路
k=nextstep(n+1);
if(k!=0)returnk;
}
return0;
}
intmigong(){//行走迷宮初始化
place[0][0]=fx;place[0][1]=fy;
returnnextstep(1);
}
voidprintit(){//顯示迷宮
inti,j;
for(i=1;i<=19;i++){
for(j=1;j<=19;j++)
if(a[i][j]==2)printf("");
elseprintf("%2d",a[i][j]);
printf(" ");
}
}
intmain(){
chars[20][20]={
"0000000000000000000",
"0111111111111111111",
"0000000001000001000",
"0111110101111101111",
"0001010100000100000",
"0101010101110111111",
"0101000100010000010",
"0111111111110111111",
"0100000000010100000",
"0101111111010101111",
"0101000111010101010",
"0111011111010111010",
"0100010000000100010",
"0101011111110101111",
"0101000000010101011",
"0101010101011101011",
"0101010101000001011",
"1101110111111111010",
"0000000000000000000"
};
inti,j,n;
for(i=1;i<=19;i++)
for(j=1;j<=19;j++)
a[i][j]=s[i-1][j-1]-48;
//顯示迷宮
printf("原始迷宮模樣 ");
printit();
n=migong();
if(n==0)
printf("沒有路徑到達 ");
else{
for(i=0;i<=n;i++)
a[place[i][0]][place[i][1]]=2;
printf("走迷宮的路徑顯示 ");
printit();
}
}
⑶ python走迷宮演算法題怎麼解
示例：
#coding:UTF-8
globalm,n,path,minpath,pathnum
m=7
n=7
k=[0,1,2,3,4,5,6,7]#循環變數取值范圍向量
a=[[0,0,1,0,0,0,0,0],
[1,0,1,0,1,1,1,0],
[0,0,0,0,1,0,0,0],
[1,1,1,1,1,0,0,0],
[0,0,0,0,0,1,1,0],
[0,0,0,0,0,0,0,0],
[0,0,1,1,1,1,1,1],
[0,0,0,0,0,0,0,0]]#迷宮矩陣
b=[[1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]] #狀態矩陣
path=[]
minpath=[]
min=10000
step=0
pathnum=0
#print(a)
#print(b)
defnextone(x,y):
globalpath,minpath,m,n,min,step,pathnum
if(x==0)and(y==0):
path=[]
step=0
if(x==m)and(y==n):
pathnum+=1
print("step=",step)
print("path=",path)
ifstep<min:
min=step
minpath=path[:]
else:
if(x+1ink)and(yink):
if(b[x+1][y]==0)and(a[x+1][y]==0):
b[x+1][y]=1
path.append([x+1,y])
step+=1
nextone(x+1,y)
step-=1
path.remove([x+1,y])
b[x+1][y]=0#回溯
if(xink)and(y+1ink):
if(b[x][y+1]==0)and(a[x][y+1]==0):
b[x][y+1]=1
path.append([x,y+1])
step+=1
nextone(x,y+1)
step-=1
path.remove([x,y+1])
b[x][y+1]=0#回溯
if(x-1ink)and(yink):
if(b[x-1][y]==0)and(a[x-1][y]==0):
b[x-1][y]=1
path.append([x-1,y])
step+=1
nextone(x-1,y)
step-=1
path.remove([x-1,y])
b[x-1][y]=0#回溯
if(xink)and(y-1ink):
if(b[x][y-1]==0)and(a[x][y-1]==0):
b[x][y-1]=1
path.append([x,y-1])
step+=1
nextone(x,y-1)
step-=1
path.remove([x,y-1])
b[x][y-1]=0#回溯
nextone(0,0)
print()
print("min=",min)
print("minpath=",minpath)
print("pathnum=",pathnum)
⑷ c語言迷宮問題，求該演算法的時間和空間的復雜度。寫出求解的過程，比如如下的求解格式
時間復雜度應該是O（n）吧，因為每個迷宮上的位置最多入棧一次。空間復雜度應該也一樣吧。
⑸ 編程：走迷宮。不會反復走重復的路徑
簡單點說叫做尋路，涉及到深度優先搜索和廣度優先搜索，當然在存在類似「戰爭迷霧」效果的同時還要涉及到動態規劃和回溯。
⑹ 數據結構演算法 用C++ 迷宮最短路徑
一般迷宮尋路可以用遞歸的演算法，或者用先進後出的棧數據結構實現
用的是深度優先的演算法，可以尋找到走出迷宮的路徑
但本題要求求出最短的路徑，這就要使用廣度優先的演算法
一般在程序中需要用到先進先出的隊列數據結構
下面是程序的代碼，主要原理是用到
quei，quej和prep三個數組來構成隊列
分別儲存路徑的行，列坐標和上一個節點在隊列中的位置
大致演算法如下，右三個嵌套的循環實現
首先是第一個節點進入隊列
當隊列不空（循環1）
｛
遍歷隊列中每節點(循環2）
｛
將八個方向能夠走的節點加入隊列（循環3）
｝
舊的節點出列
｝
#include<iostream>
#include<ctime>
usingnamespacestd;
#defineMAXNUM50
voidmain()
{
intm,n,i,j,x;
cout<<"請輸入迷宮大小"<<endl;
cin>>m>>n;
intmaze[MAXNUM][MAXNUM];
srand((int)time(NULL));
for(i=0;i<=m+1;i++){
for(j=0;j<=n+1;j++){
if(i==0||j==0||i==m+1||j==n+1)
maze[i][j]=1;
else
{
x=rand()%1000;
if(x>700){maze[i][j]=1;}//控制矩陣中1的個數，太多1迷宮很容易走不通
else{maze[i][j]=0;}
}
cout<<maze[i][j]<<'';
}
cout<<endl;
}
//以上是輸入和迷宮生成，一下是走迷宮
intmove[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
int*quei=newint[m*n];//儲存行坐標隊列
int*quej=newint[m*n];//儲存列坐標隊列
int*prep=newint[m*n];//儲存之前一步在隊列中的位置
inthead,rear,length;//隊列頭，隊列尾，隊列長度
head=0;rear=1;length=1;
quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置進隊列
intpos;//當前節點在隊列中的位置，
intii,jj,ni,nj;//當前節點的坐標，新節點的坐標
intdir;//移動方向
if(maze[1][1]==1)length=0;//第一點就不能通過
elsemaze[1][1]=1;
while(length)//隊列非空繼續
{
for(pos=head;pos<head+length;pos++)//尋找這一層所有節點
{
ii=quei[pos];jj=quej[pos];//當前位置坐標
if(ii==m&&jj==n)break;
for(dir=0;dir<8;dir++)//尋找8個方向
{
ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐標
if(maze[ni][nj]==0)//如果沒有走過
{
quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新節點入隊
rear=rear+1;
maze[ni][nj]=1;//標記已經走過
}
}
}
if(ii==m&&jj==n)break;
head=head+length;
length=rear-head;//這一層節點出列
}
if(ii==m&&jj==n)
{
while(pos!=-1)
{
cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
pos=prep[pos];
if(pos!=-1)cout<<',';
}
}
else
{
cout<<"THEREISNOPATH."<<endl;
}
delete[]quei;
delete[]quej;
delete[]prep;
}
⑺ C語言迷宮問題，求該演算法的時間和空間的復雜度。迷宮的路徑已經定義好，求出路的演算法。
該演算法是不穩定的，其時空復雜度不僅和m,n有關，還和mg[][]的具體數值有關。
最壞情況下：每個點都試探過才走到終點。此時時間復雜度為：(m*n-1)*4，（其中4為4個方向），空間復雜度m*n*2，(其中m*n為存儲迷宮圖空間，m*n為棧空間);
再好情況下：一次試探過就走到終點。此時時間復雜度為：(min(m,n)-1)，空間復雜度m*n;
所以：
該演算法時間復雜度為：[(m*n-1)*4+(min(m,n)-1)]/2，約為2×m×n
空間復雜度為3*m*n/2
⑻ 深度優先演算法的例1.迷宮問題
實現這一演算法，我們要用到編程的一大利器--遞歸。「遞歸」是一個很抽象的概念， 但是在日常生活中，我們還是能夠看到的。拿兩面鏡子來，把他們面對著面，你會看到什麼？你會看到鏡子中 有無數個鏡子？怎麼回事？A鏡子中有B鏡子的象，B鏡子中有A鏡子的象，A鏡子的象就是A鏡子本身的真實寫照，也就是說A鏡子的象包括了A鏡子，還有B鏡子在A鏡子中的象………………好累啊，又煩又繞口，還不好理解。換成計算機語言就是A調用B，而B又調用A，這樣間接的，A就調用了A本身，這實現了一個重復的功能。
再舉一個例子：從前有座山，山裡有座廟，廟里有個老和尚，老和尚在講故事，講什麼呢？講：從前有座山，山裡有座廟，廟里有個老和尚，老和尚在講故事，講什麼呢？講：從前有座山，山裡有座廟，廟里有個老和尚， 老和尚在講故事，講什麼呢？講：…………。好傢伙，這樣講到世界末日還講不完，老和尚講的故事實際上就是前面的故事情節，這樣不斷地調用程序本身，就形成了遞歸。 萬一這個故事中的某一個老和尚看這個故事不順眼，就把他要講的故事換成：「你有完沒完啊！」，這樣，整個故事也就嘎然而止了。我們編程就要注意這一點，在適當的時候，就必須要有一個這樣的和尚挺身而出，把整個故事給停下來，或者使他不再往深一層次搜索，要不，遞歸就會因計算機存儲容量的限制而被迫溢出，切記，切記。 這是一道很經典的題目了，我們先要明確一下思路，如何運用深度優先搜索法，完 成這道題目。我們先建立一個8*8格的棋盤，在棋盤的第一行的任意位置安放一隻皇後。緊接著，我們就來放 第二行，第二行的安放就要受一些限制了，因為與第一行的皇後在同一豎行或同一對角線的位置上是不能安放 皇後的，接下來是第三行，……，或許我們會遇到這種情況，在擺到某一行的時候，無論皇後擺放在什麼位 置，她都會被其他行的皇後吃掉，這說明什麼呢？這說明，我們前面的擺放是失敗的，也就是說，按照前面 的皇後的擺放方法，我們不可能得到正確的解。那這時怎麼辦？改啊，我們回到上一行，把原先我們擺好的 皇後換另外一個位置，接著再回過頭擺這一行，如果這樣還不行或者上一行的皇後只有一個位置可放，那怎 么辦？我們回到上一行的上一行，這和老鼠碰了壁就回頭是一個意思。就這樣的不斷的嘗試，修正,我們最終會得到正確的結論的。
⑼ 數據結構演算法（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語言數據結構 老鼠走迷宮問題
/* 迷宮矩陣
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 1 0 0 0 1
1 1 1 0 0 1 0 1 0 1
1 0 0 0 1 0 0 0 0 1
1 0 0 0 0 1 0 1 0 1
1 1 0 1 0 0 0 0 0 1
1 0 0 1 1 1 0 1 1 1
1 1 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1
*/
#include<stdio.h>
#define m 7
#define n 8
void path()
{
int maze[m+2][n+2] ;
int move[4][2]={ {0,-1},{-1,0},{0,1},{1,0} };
int s[54][3];
int top=0;
int i,j,k,f=0;
int g,h,p;
for(i=0;i<m+2;++i)
for(j=0;j<n+2;++j)
scanf("%d",&maze[i][j]);
maze[1][1]=2;
s[top][0]=1;
s[top][1]=1;
s[top][2]=0;
++top;
while(top!=0&&f==0)
{
--top;
i=s[top][0];
j=s[top][1];
k=s[top][2];
while(k<4)
{
g=i+move[k][0];
h=j+move[k][1];
if(g==m&&h==n&&maze[g][h]==0)
{
for(p=0;p<top;++p)
printf("%3d,%d\n",s[p][0],s[p][1]);
printf("%3d,%d\n",i,j);
printf("%3d,%d\n",m,n);
f=1;
}//if
if(maze[g][h]==0)
{
maze[g][h]=2;
s[top][0]=i;
s[top][1]=j;
s[top][2]=k;
++top;
i=g;
j=h;
k=0;
}//if
k=k+1;
}//while
}//while
if(f==0)
printf("no path\n");
}//pathvoid main()
{
path();
}