将从迷宫入口到各点
最短路近集合看作
棵树
用广度遍历思路方法即可找到出口最短路近本
算法思想来源于求图上点到其余各点最短路近
Dijkstra算法/* 迷宫探路III(最短路径)*/
/* DIJKSTRAMAZE.C */
/* 2003-8-26 */
#
<stdlib.h>#
<time.h>#
<math.h>#
<stdio.h>#
<graphics.h>#
N 22#
M 22
bg[M][N]; aa[M][N];struct pace{
pre; x; y; ri; rj;}road[M*N];
struct pace bestroad[M*N];
void makebg(
,);void drawbg(
,,,,,);void drawman(
,,);void rect(
,,,);void
{/* 开始 */ step=20; len=10; size=20; x=0,y=0; i=0,j=0; gdriver=DETECT,gmode;char ch;
direc; routelen=0; dj={-1,1,0,0}; di={0,0,-1,1}; begin; end; k; t; num; suc; cnt; x0; y0; le; tmp;makebg(M,N);
/*registerbgidriver(EGAVGA_driver);
initgraph(&gdriver,&gmode,\"c:\\\\turboc2\");*/
initgraph(&gdriver,&gmode,\"c:\\\\tc20\\\\bgi\");
cleardevice
;
writemode(XOR_PUT);textstyle(1,0,3);color(GREEN);outtextxy(100,180,\"DIJKSTRA MAZE\");
color(BLUE);fillstyle(LINE_FILL,BLUE);/*drawbg(bg,M,N,size,0,0);*/
drawbg(aa,M,N,size,0,0);
color(WHITE);x
len;ylen;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];
(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;
(iN-1&&jM-1){suc=1;
;}
}
}
(suc);}
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
;}
/*
结束 *//* 绘制小人 */
void drawman(
x, y, len){ 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(
bg[N], a, b, size, x, y){ startx=x; i,j;for(i=0;i<a;i
){for(j=0;j<b;j
){(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(
x0, y0, x1, y1){ i,j;for(i=x0;i<=x1;i
)line(i,y0,i,y1);
}
/* 随机生成代表迷宫地图
*/void makebg(
a, b){ i,j; ran; 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;
(i>=M-1&&j>=N-1);ran=(
)rand*4;(ran<1){(direc!=1&&i<a-1){i
;direc=3;
}
}
(ran<2){(direc!=2&&j>0){j--;
direc=0;
}
}
(ran<3){(direc!=3&&i>0){i--;
direc=1;
}
}
{(direc!=0&&j<b-1){j
;direc=2;
}
}
}
/* 随机生成迷宫其余部分 */
for(i=0;i<a;i
)for(j=0;j<b;j
)(bg[i][j]1){ran=(
)rand*10;(ran<5)bg[i][j]=0;}
for(i=0;i<a;i
)for(j=0;j<b;j
){(bg[i][j]1)aa[i][j]=-1; aa[i][j]=0;}
}
=span_ad>
最新评论