📄 迷宫探路iii(最短路径)_数据结构与算法_数据结构算法_c语言_c 语言之家.htm
字号:
width="100%">
<TBODY>
<TR>
<TD align=middle vAlign=top width="95%">
<TABLE border=1 borderColor=#e2ca9f cellPadding=0 cellSpacing=0
width="100%">
<TBODY>
<TR>
<TD align=middle
background="迷宫探路III(最短路径)_数据结构与算法_数据结构算法_C语言_C 语言之家.files/002.jpg"
borderColor=#e2ca9f vAlign=top width="69%">
<TABLE align=center border=0 cellPadding=0 cellSpacing=0
width="100%">
<TBODY>
<TR>
<TD height=40 width="100%"></TD></TR>
<TR>
<TD>
<FORM action=Readnews.asp?newsid=2584&id2=2584
method=post name=form1>
<CENTER><!-- <input type=submit name=aa value="点击关闭浮动图标" width=20 title="点击广告支持本站">--></CENTER></FORM></TD></TR>
<TR>
<TD align=middle bgColor=#dddddd height=20
style="FONT-SIZE: 18px" vAlign=bottom
width="85%"><STRONG><FONT color=#003399
size=4><B>迷宫探路III(最短路径) </B></FONT></STRONG></TD><BR></TR>
<TR>
<TD align=middle width="100%"><BR></TD></TR>
<TR>
<TD align=middle style="FONT-SIZE: 9pt"
width="100%">发表日期：2003年10月15日 出处：朱清 作者：朱清 已经有2879位读者读过此文</TD></TR>
<TR>
<TD align=middle width="100%"><!--下面的这一句是设置阅读文本区的宽度-->
<TABLE align=center border=0 cellPadding=0 cellSpacing=0
style="TABLE-LAYOUT: fixed" width="90%">
<TBODY>
<TR>
<TD align=middle width="100%"></TD></TR>
<TR>
<TD style="WORD-WRAP: break-word"><FONT
class=news><BR>
<P> 将从迷宫入口到各点的最短路近的集合看作一棵树。用广度遍历<BR> 的方法即可找到出口的最短路近。本程序算法思想来源于求图上一点<BR> 到其余各点最短路近的Dijkstra算法。</P>
<P> /* 迷宫探路III（最短路径）*/<BR>/* DIJKSTRAMAZE.C
*/<BR>/* 2003-8-26 */<BR>#include
<stdlib.h><BR>#include
<time.h><BR>#include
<math.h><BR>#include
<stdio.h><BR>#include
<graphics.h><BR>#define N 22<BR>#define M
22<BR>int bg[M][N];<BR>int aa[M][N];<BR>struct
pace{<BR> int
pre;<BR> int
x;<BR> int
y;<BR> int
ri;<BR> int
rj;<BR>}road[M*N];<BR>struct pace
bestroad[M*N];</P>
<P><BR>void makebg(int,int);<BR>void
drawbg(int[][],int,int,int,int,int);<BR>void
drawman(int,int,int);<BR>void
rect(int,int,int,int);</P>
<P>void main(){/* main()开始 */<BR>int
step=20;<BR>int len=10;<BR>int size=20;<BR>int
x=0,y=0;<BR>int i=0,j=0;<BR>int
gdriver=DETECT,gmode;<BR>char ch;<BR>int
direc;<BR>int routelen=0;<BR>int
dj[]={-1,1,0,0};<BR>int di[]={0,0,-1,1};<BR>int
begin;<BR>int end;<BR>int k;<BR>int t;<BR>int
num;<BR>int suc;<BR>int cnt;<BR>int x0;<BR>int
y0;<BR>int le;<BR>int
tmp;<BR>makebg(M,N);<BR>/* registerbgidriver(EGAVGA_driver);<BR> initgraph(&gdriver,&gmode,"c:\\turboc2");*/<BR> initgraph(&gdriver,&gmode,"c:\\tc20\\bgi");
<BR>cleardevice();<BR>setwritemode(XOR_PUT);<BR>settextstyle(1,0,3);<BR>setcolor(GREEN);<BR>outtextxy(100,180,"DIJKSTRA
MAZE");<BR>setcolor(BLUE);<BR>setfillstyle(LINE_FILL,BLUE);</P>
<P>/*drawbg(bg,M,N,size,0,0);*/<BR>drawbg(aa,M,N,size,0,0);<BR>setcolor(WHITE);<BR>x+=len;y+=len;<BR>drawman(x,y,len);<BR>x0=x;y0=y;<BR>/*
电脑控制
*/<BR>i=j=0;<BR>aa[0][0]=1;<BR>begin=0;<BR>end=0;<BR>road[0].ri=0;<BR>road[0].rj=0;<BR>road[0].x=x0;<BR>road[0].y=y0;<BR>road[0].pre=-1;<BR>le=1;<BR>suc=0;<BR>while(!suc){<BR>cnt=0;<BR>le++;<BR>for(k=begin;k<=end;k++){<BR>
for(t=0;t<4;t++){<BR>
x=road[k].x+dj[t]*step;<BR>
y=road[k].y+di[t]*step
;<BR>
i=road[k].ri+di[t];<BR>
j=road[k].rj+dj[t];<BR>
if(i<M&&i>=0&&j<N&&j>=0&&aa[i][j]==0){<BR>
cnt++;<BR>
aa[i][j]=le;<BR>
road[end+cnt].pre=k;<BR>
road[end+cnt].x=x;<BR>
road[end+cnt].y=y;<BR>
road[end+cnt].ri=i;<BR>
road[end+cnt].rj=j;<BR>
if(i==N-1&&j==M-1){<BR>
suc=1;<BR>
break;<BR>
}<BR>
}<BR> }<BR>
if(suc)break;<BR>}<BR>begin=end+1;<BR>end=end+cnt;<BR>}<BR>/*
output
*/<BR>i=end;j=0;<BR>while(i!=-1){<BR>
bestroad[j].x=road[i].x;<BR>
bestroad[j].y=road[i].y;<BR>
bestroad[j].ri=road[i].ri;<BR>
bestroad[j].rj=road[i].rj;<BR>
i=road[i].pre;<BR>
j++;<BR>}<BR>for(i=0;i<j/2;i++){<BR>
tmp=bestroad[i].x;<BR>
bestroad[i].x=bestroad[j-1-i].x;<BR>
bestroad[j-1-i].x=tmp;<BR>
tmp=bestroad[i].y;<BR>
bestroad[i].y=bestroad[j-1-i].y;<BR>
bestroad[j-1-i].y=tmp;<BR>}<BR>getch();<BR>drawman(x0,y0,len);<BR>for(i=0;i<j;i++){<BR>
drawman(bestroad[i].x,bestroad[i].y,len);<BR>
delay(80000);<BR>
drawman(bestroad[i].x,bestroad[i].y,len);<BR>}<BR>i--;<BR>drawman(bestroad[i].y,bestroad[i].x,len);<BR>getch();<BR>closegraph();<BR>}<BR>/*
main()结束 */</P>
<P>/* 绘制小人 */<BR>void drawman(int x,int y,int
len){<BR> int
r=len/4;<BR>
rect(x-r,y-len,x+r,y-len+2*r);<BR>
line(x,y-len+2*r,x,y);<BR>
line(x-len,y,x+len,y);<BR>
line(x,y,x-len,y+len);<BR>
line(x,y,x+len,y+len);<BR>}<BR>/* 绘制迷宫地图
*/<BR>void drawbg(int bg[][N],int a,int b,int
size,int x,int y){<BR> int
startx=x;<BR> int
i,j;<BR>
for(i=0;i<a;i++){<BR>
for(j=0;j<b;j++){<BR>
if(bg[i][j]==-1)<BR>
rect(x,y,x+size-1,y+size-1);<BR>
x+=size;<BR>
}<BR>
x=startx;<BR>
y+=size;<BR>
}<BR>
rectangle(0,0,size*b,size*a);<BR>
line(0,0,size,0);line(0,0,0,size);<BR>
line(size*b,size*(a-1),size*b,size*a);<BR>
line(size*(b-1),size*a,size*b,size*a);<BR>}<BR>/*
绘制实心矩形 */<BR>void rect(int x0,int y0,int x1,int
y1){<BR> int
i,j;<BR>
for(i=x0;i<=x1;i++)<BR>
line(i,y0,i,y1);<BR>}</P>
<P>/* 随机生成代表迷宫地图的数组 */<BR>void makebg(int
a,int b){<BR> int
i,j;<BR> int
ran;<BR> int direc;<BR>/*
初始化迷宫地图 */<BR>
for(i=0;i<a;i++)<BR>
for(j=0;j<b;j++)<BR>
bg[i][j]=1;</P>
<P>/* 随机生成迷宫通路 */<BR>
randomize();<BR>
i=j=0;direc=2;<BR> while(1){</P>
<P>
bg[i][j]=0;<BR>
if(i>=M-1&&j>=N-1)break;<BR>
ran=(int)rand()*4;<BR>
if(ran<1){<BR>
if(direc!=1&&i<a-1){<BR>
i++;<BR>
direc=3;<BR>
}<BR>
}
<BR>
else
if(ran<2){<BR>
if(direc!=2&&j>0){<BR>
j--;<BR>
direc=0;<BR>
}<BR>
}<BR>
else
if(ran<3){<BR>
if(direc!=3&&i>0){<BR>
i--;<BR>
direc=1;<BR>
}<BR>
}<BR>
else
{<BR>
if(direc!=0&&j<b-1){<BR>
j++;<BR>
direc=2;
<BR>
}<BR>
}<BR> }<BR>/*
随机生成迷宫其余部分 */<BR>
for(i=0;i<a;i++)<BR>
for(j=0;j<b;j++)<BR>
if(bg[i][j]==1){<BR>
ran=(int)rand()*10;<BR>
if(ran<5)bg[i][j]=0;<BR>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -