实例编程：迷宫探路III

核心提示：将从迷宫入口到各点的最短路近的集合看作一棵树，用广度遍历的方法即可找到出口的最短路近，实例编程：迷宫探路III，本程序算法思想来源于求图上一点到其余各点最短路近的Dijkstra算法，/* 迷宫探路III（最短路径）*//* DIJKSTRAMAZE.C *//* 2003-8-26 */#include <st

将从迷宫入口到各点的最短路近的集合看作一棵树。用广度遍历的方法即可找到出口的最短路近。本程序算法思想来源于求图上一点到其余各点最短路近的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;

　　 }

　　}