將從迷宮入口到各點的最短路近的集合看作一棵樹。用廣度遍歷的方法即可找到出口的最短路近。本程序算法思想來源於求圖上一點到其余各點最短路近的Dijkstra算法。
/* 迷宮探路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();
}
/* main()結束 */
/* 繪制小人 */
void drawman(int x,int y,int len){
int r=len/4;
rect(x-r,y-len,x+r,y-len+2*r);
line(x,y-len+2*r,x,y);
line(x-len,y,x+len,y);
line(x,y,x-len,y+len);
line(x,y,x+len,y+len);
}
/* 繪制迷宮地圖 */
void drawbg(int bg[][N],int a,int b,int size,int x,int y){
int startx=x;
int i,j;
for(i=0;i<a;i++){
for(j=0;j<b;j++){
if(bg[i][j]==-1)
rect(x,y,x+size-1,y+size-1);
x+=size;
}
x=startx;
y+=size;
}
rectangle(0,0,size*b,size*a);
line(0,0,size,0);line(0,0,0,size);
line(size*b,size*(a-1),size*b,size*a);
line(size*(b-1),size*a,size*b,size*a);
}
/* 繪制實心矩形 */
void rect(int x0,int y0,int x1,int y1){
int i,j;
for(i=x0;i<=x1;i++)
line(i,y0,i,y1);
}
/* 隨機生成代表迷宮地圖的數組 */
void makebg(int a,int b){
int i,j;
int ran;
int direc;
/* 初始化迷宮地圖 */
for(i=0;i<a;i++)
for(j=0;j<b;j++)
bg[i][j]=1;
/* 隨機生成迷宮通路 */
randomize();
i=j=0;direc=2;
while(1){
bg[i][j]=0;
if(i>=M-1&&j>=N-1)break;
ran=(int)rand()*4;
if(ran<1){
if(direc!=1&&i<a-1){
i++;
direc=3;
}
}
else if(ran<2){
if(direc!=2&&j>0){
j--;
direc=0;
}
}
else if(ran<3){
if(direc!=3&&i>0){
i--;
direc=1;
}
}
else {
if(direc!=0&&j<b-1){
j++;
direc=2;
}
}
}
/* 隨機生成迷宮其余部分 */
for(i=0;i<a;i++)
for(j=0;j<b;j++)
if(bg[i][j]==1){
ran=(int)rand()*10;
if(ran<5)bg[i][j]=0;
}
for(i=0;i<a;i++)
for(j=0;j<b;j++){
if(bg[i][j]==1)aa[i][j]=-1;
else aa[i][j]=0;
}
}
