迷宮探路III(最短路徑)

字號： 小 中 大

將從迷宮入口到各點(diǎn)的最短路近的集合看作一棵樹。用廣度遍歷的方法即可找到出口的最短路近。本程序算法思想來源于求圖上一點(diǎn)到其余各點(diǎn)最短路近的Dijkstra算法。
     /* 迷宮探路III（最短路徑）*/
    /* DIJKSTRAMAZE.C */
    /* 2003-8-26 */
    #include
    #include
    #include
    #include
    #include
    #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=0&&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     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     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();
    }