迷宮最短路徑演算法
Ⅰ 挑戰程序設計競賽上的問題，迷宮的最短路徑
typedefpair<int,int>p;
這就是p的定義啊，p是一個類型
至於 pair 還是學一下比較好，很常用的。
pair 的定義大概是這樣：
template<class_T1,class_T2>
structpair
{
_T1first;
_T2second;
//....
}
Ⅱ 迷宮最短路徑
用堆棧不一定能得出最短路徑，改用隊列可以實現最短路徑，下面是《數據結構演算法與應用-C++語言描述》裡面的一段話。
[迷宮老鼠] 使用F I F O分枝定界，初始時取（1，1）作為E-節點且活動隊列為空。迷宮的位置（1 , 1）被置為1，以免再次返回到這個位置。（1，1）被擴充，它的相鄰節點（1，2）和（2，1）加入到隊列中（即活節點表）。為避免再次回到這兩個位置，將位置（ 1，2）和（2，1）置為1。
1 1 0
1 1 1
0 0 0
a）
1 1 1
1 1 1
0 0 0
b）
1 1 1
1 1 1
1 0 0
c）
節點（1，2）從隊列中移出並被擴充。檢查它的三個相鄰節點（見圖1 6 - 1的解空間），只有
（1，3）是可行的移動（剩餘的兩個節點是障礙節點），將其加入隊列，並把相應的迷宮位置置
為1，所得到的迷宮狀態如圖17-1b 所示。節點（1，2）被刪除，而下一個E-節點（2，1）將
會被取出，當此節點被展開時，節點（3，1）被加入隊列中，節點（3，1）被置為1，節點（2，
1）被刪除，所得到的迷宮如圖17-1c 所示。此時隊列中包含（1，3）和（3，1）兩個節點。隨
後節點（1，3）變成下一個E-節點，由於此節點不能到達任何新的節點，所以此節點即被刪除，
節點（3，1）成為新的E-節點，將隊列清空。節點（3，1）展開，（3，2）被加入隊列中，而
（3，1）被刪除。（3，2）變為新的E-節點，展開此節點後，到達節點（3，3），即迷宮的出口。
使用F I F O搜索，總能找出從迷宮入口到出口的最短路徑。
Ⅲ 求一個求從迷宮的一點到另一點的最短路徑的遞歸演算法
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;
}
Ⅳ 如何用C語言實現求迷宮的最短路徑
#include<stdio.h>
#include<stdlib.h>
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定義迷宮，0表示能走的塊，1表示不能走，在外圍加上一圈不能走的塊
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,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}
};
struct
{
int i,j; //塊的位置
int pre; //本路徑中上一塊在隊列中的下標
}Qu[Max];
int front=-1,rear=-1;
void print(int n);
int mgpath(int xi,int yi,int xe,int ye) //搜索演算法
{
int i,j,find=0,di;
rear++;
Qu[rear].i=xi;
Qu[rear].j=yi;
Qu[rear].pre=-1;
mg[1][1]=-1;
while(front<=rear&&!find)
{
front++;
i=Qu[front].i;
j=Qu[front].j;
if(i==xe&&j==ye)
{
find=1;
print(front);
return(1);
}
for(di=0;di<4;di++)
{
switch(di) //四個方向
{
case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break;
}
if(mg[i][j]==0)
{
rear++;
Qu[rear].i=i;
Qu[rear].j=j;
Qu[rear].pre=front;
mg[i][j]=-1; //避免死循環
}
}
}
return 0;
}
void print(int n) //輸出 路徑演算法
{
int k=n,j,m=1;
printf("\n");
do //將輸出的路徑上的所有pre改為-1
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf("迷宮最短路徑如下：\n");
k=0;
while(k<Max)
{
if(Qu[k].pre==-1)
{
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(m%5==0)
printf("\n");
m++;
}
k++;
}
printf("\n");
}
int main()
{
mgpath(1,1,M,N);
system("pause");
return 0;
}
Ⅳ 迷宮數組 最短路徑演算法 我， 我， 我給分60！
//對角線也可以走：如從1,3到2,4最短路徑為根號2
//如果對角線不想，兩個for循環條件判斷稍微修改下：
//代碼如下：
//輸出-1 表示找不到路徑
/*
給個數組，0表示通路，1表示阻礙，然後給任意兩個0的坐標，可以找到它們之間的最短路徑並列印出來
比如說數組是 1 0 0 0 1
1 1 1 0 1
1 1 0 0 1
1 0 0 0 1
1 0 1 1 1
然後我就可以找到第一行第二個數和第五行第二個數之間的最短路徑了
*/
#include <stdlib.h>
#include <math.h>
#include <windows.h>
#include <stdio.h>
#define M 5
#define N 5
typedef struct coordinate{
short int x;
short int y;
} COORDINATE;
COORDINATE path[M*N];//全局變數，存儲已訪問結點
float getminpath(COORDINATE *,COORDINATE *,char [][N],COORDINATE *);
void main()
{
memset(path,0,sizeof(COORDINATE)*M*N);
char maze[M][N]={
'\1','\0','\0','\0','\1',
'\1','\1','\1','\0','\1',
'\1','\1','\0','\0','\1',
'\1','\0','\0','\0','\1',
'\1','\0','\1','\1','\1',
};
COORDINATE a,b;
float dis;
do{
system("cls");
printf("請輸入起點坐標：\n如1,2為第一行第二個數\n");
printf("取值范圍1～%d,1～%d\n",M,N);
scanf("%hd,%hd",&a.x,&a.y);
printf("請輸入終點坐標：\n如5,2為第五行第二個數\n");
printf("取值范圍1～%d,1～%d\n",M,N);
scanf("%hd,%hd",&b.x,&b.y);
a.x--;
a.y--;
b.x--;
b.y--;
dis=getminpath(&a,&b,maze,path);
printf("最短路徑為：%f\n",dis);
system("pause");
} while(getchar()!=EOF);
}
float getminpath(COORDINATE *from,COORDINATE *to,char maze[][5],COORDINATE *visited)
//從from結點到to結點可以分成兩步，1.從from到from的相鄰結點。2.再到to結點，這就是一個遞歸的過程
//將已訪問結點存放入visited中
{
COORDINATE *nearpt=(COORDINATE*)malloc(sizeof(COORDINATE)*1);
memset(nearpt,0,sizeof(COORDINATE));
int i,j;
float min=0;//存儲最短路徑的值
COORDINATE *pvisit;//遍歷已訪問結點的指針
char reflag;//相鄰結點是否 「已訪問」 的flag
float dis=-1;//距離
if(from==0||to==0||maze==0)
{
return -1;
}
else
{
if(from->x==to->x&&from->y==to->y)//坐標相同，表示已到達
{
dis=0;
}
else
{
for(i=-1;i<=1;i++)
{
for(j=-1;j<=1;j++)
{
if(i==0&&j==0)
{
continue;
}
nearpt->x=from->x+i;
nearpt->y=from->y+j;
if(nearpt->x<0||nearpt->x>M-1||nearpt->y<0||nearpt->y>N-1)//越界
{
continue;
}
if(maze[nearpt->x][nearpt->y]!='\0')//非零為障礙，繼續下一次循環
{
continue;
}
reflag='\0';//初值為'\0'，表示未訪問過
for(pvisit=path;pvisit<visited;pvisit++)//搜索已訪問結點
{
if(pvisit->x==nearpt->x&&pvisit->y==nearpt->y)
{
reflag='\1';//該結點已經訪問過了
break;
}
}
if(reflag=='\1')
{
continue;
}
else
{
visited->x=from->x;//將from結點加入已訪問結點數組中
visited->y=from->y;
dis=getminpath(nearpt,to,maze,visited+1);//遞歸
if(dis>=0)
{
dis+=sqrt((nearpt->x-from->x)*(nearpt->x-from->x)+(nearpt->y-from->y)*(nearpt->y-from->y));
// printf("%d,%d到%d,%d\t距離：%3f\n",from->x,from->y,to->x,to->y,dis);
if(min==0)//第一次，還沒將dis的值賦給m過
{
min=dis;
}
else
{
if(dis<min)
{
min=dis;
}
else
{
}
}
}
visited->x=0;//清除from結點
visited->y=0;
}
}
}
}
}
free(nearpt);
if(min>0)
{
return min;
}
else
{
return dis;
}
}
Ⅵ 迷宮探路III（最短路徑）
/* 迷宮探路III（最短路徑）*/
/* DIJKSTRAMAZE.C */
/* 2003-8-26 */
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <graphics.h>
#define N 22
#define M 22
int bg[M][N];
int aa[M][N];
struct pace{
int pre;
int x;
int y;
int ri;
int rj;
}road[M*N];
struct pace bestroad[M*N];
void makebg(int,int);
void drawbg(int[][],int,int,int,int,int);
void drawman(int,int,int);
void rect(int,int,int,int);
void main(){/* main()開始 */
int step=20;
int len=10;
int size=20;
int x=0,y=0;
int i=0,j=0;
int gdriver=DETECT,gmode;
char ch;
int direc;
int routelen=0;
int dj[]={-1,1,0,0};
int di[]={0,0,-1,1};
int begin;
int end;
int k;
int t;
int num;
int suc;
int cnt;
int x0;
int y0;
int le;
int tmp;
makebg(M,N);
/* registerbgidriver(EGAVGA_driver);
initgraph(&gdriver,&gmode,"c:\\turboc2");*/
initgraph(&gdriver,&gmode,"c:\\tc20\\bgi");
cleardevice();
setwritemode(XOR_PUT);
settextstyle(1,0,3);
setcolor(GREEN);
outtextxy(100,180,"DIJKSTRA MAZE");
setcolor(BLUE);
setfillstyle(LINE_FILL,BLUE);
/*drawbg(bg,M,N,size,0,0);*/
drawbg(aa,M,N,size,0,0);
setcolor(WHITE);
x+=len;y+=len;
drawman(x,y,len);
x0=x;y0=y;
/* 電腦控制 */
i=j=0;
aa[0][0]=1;
begin=0;
end=0;
road[0].ri=0;
road[0].rj=0;
road[0].x=x0;
road[0].y=y0;
road[0].pre=-1;
le=1;
suc=0;
while(!suc){
cnt=0;
le++;
for(k=begin;k<=end;k++){
for(t=0;t<4;t++){
x=road[k].x+dj[t]*step;
y=road[k].y+di[t]*step ;
i=road[k].ri+di[t];
j=road[k].rj+dj[t];
if(i<M&&i>=0&&j<N&&j>=0&&aa[i][j]==0){
cnt++;
aa[i][j]=le;
road[end+cnt].pre=k;
road[end+cnt].x=x;
road[end+cnt].y=y;
road[end+cnt].ri=i;
road[end+cnt].rj=j;
if(i==N-1&&j==M-1){
suc=1;
break;
}
}
}
if(suc)break;
}
begin=end+1;
end=end+cnt;
}
/* output */
i=end;j=0;
while(i!=-1){
bestroad[j].x=road[i].x;
bestroad[j].y=road[i].y;
bestroad[j].ri=road[i].ri;
bestroad[j].rj=road[i].rj;
i=road[i].pre;
j++;
}
for(i=0;i<j/2;i++){
tmp=bestroad[i].x;
bestroad[i].x=bestroad[j-1-i].x;
bestroad[j-1-i].x=tmp;
tmp=bestroad[i].y;
bestroad[i].y=bestroad[j-1-i].y;
bestroad[j-1-i].y=tmp;
}
getch();
drawman(x0,y0,len);
for(i=0;i<j;i++){
drawman(bestroad[i].x,bestroad[i].y,len);
delay(80000);
drawman(bestroad[i].x,bestroad[i].y,len);
}
i--;
drawman(bestroad[i].y,bestroad[i].x,len);
getch();
closegraph();
Ⅶ 數據結構演算法 用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;
}
Ⅷ 迷宮最短路徑演算法，時間復雜度最低的是那種
http://..com/question/24452924.html?si=5
Ⅸ 怎樣求得迷宮中的的最短路徑
建議採用雙向廣度優先搜索演算法，對於迷宮問題貌似是最高效的演算法了
Ⅹ 用圖論做一個求迷宮最短路徑的演算法
以起點為首節點開始分支，分支的個數就是當前節點有幾個位置可以走，節點內容為當前所在迷宮位置
就這樣不停的分支，每生成一個節點就判斷是否為終點位置，是則得出結果，
輸出路徑。因為生成的樹的層數對應的正是已走的步數，所以第一個結果必是最短的
另外在數據結構上可以多設計一個數組記錄已經走過的位置，當生成的節點位置已經被走過，則可刪除該節點，
這樣可以減少搜索次數。
這是類似的廣度搜索，如果數據量不多，用遞歸會更直觀，簡單。