#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include<dos.h>
#define n 12
#define INFINITY 9999
#define NULL 0
#define LEN sizeof(struct CellType)
/*------------------輸出主界面-------------------*/
menu()
{
    int gdriver, gmode;
    gdriver=DETECT;             /* 屏幕分辨率為640*480 */
    registerbgidriver(EGAVGA_driver);    /* 建立獨立圖形運行程序 */
    initgraph(&gdriver, &gmode, "");

    setbkcolor(0);        /* 設置背景顏色為淡灰色 */
    setcolor(4);
    rectangle(70,50,480,350);
    setfillstyle(1,6);
    bar(70,50,480,350);
    setfillstyle(1, 15); /* 白以實填充 */
    bar(75,55,475,345);

    setcolor(6);
    line(0,50,640,50);
    line(0,350,640,350);    /* 劃出分開屏幕的線 */

    setcolor(11);
    line(100,100,250,100);
    line(100,100,100,200);
    line(100,200,250,100);
    line(250,100,400,150);
    line(250,100,300,160);
    line(400,150,300,160);
    line(400,150,350,200);
    line(400,150,350,300);
    line(400,150,450,250);
    line(100,200,170,200);
    line(100,200,150,300);
    line(300,160,170,200);
    line(300,160,350,200);
    line(300,160,250,280);
    line(170,200,250,280);
    line(170,200,150,300);
    line(450,250,450,300);
    line(250,280,350,300);
    line(350,300,450,300);
    line(100,100,170,200);
    line(250,280,150,300);
    setcolor(2);
    settextstyle(0, 0, 2);
    outtextxy(30,150,"M");
    outtextxy(30,200,"A");
    outtextxy(30,250,"P");
    setcolor(4);
    settextstyle(0, 0, 2);
    outtextxy(150,20,"Traffic Guide System");

    /*---各個旅游點----*/
    setfillstyle(1,10);
    circle(100,100,3);        /* 0 醫院：Hospital */
    floodfill(100,100,4);
    circle(100,200,3);        /* 1 火車站：Station */
    floodfill(100,200,4);

    circle(400,150,3);        /* 2 博物館:Museum */
    floodfill(400,150,4);
    circle(250,100,3);        /* 3 市政府 Government */
    floodfill(250,100,4);

    circle(300,160,3);        /* 4 公園：Park */
    floodfill(300,160,4);
    circle(170,200,3);        /* 5 購物中心：Shopping Centre */
    floodfill(170,200,4);

    circle(350,200,3);        /* 6 大學：University */
    floodfill(350,200,4);
    circle(450,250,3);        /* 7 消防站：Fire Station */
    floodfill(450,250,4);

    circle(250,280,3);        /* 8 警察局:Police Station */
    floodfill(250,280,4);
    circle(150,300,3);        /* 9 國際機場：Aerodrome */
    floodfill(150,300,4);

    circle(350,300,3);        /* 10 碼頭：Dock */
    floodfill(350,300,4);
    circle(450,300,3);        /* 11 化工廠：Chemical Plant */
    floodfill(450,300,4);

    setcolor(12);
    settextstyle(1, 0, 4);   /* 三重筆劃字體, 水平放大8倍 */
    outtextxy(90,100,"0");
    outtextxy(90,200,"1");
    outtextxy(410,150,"2");
    outtextxy(250,90,"3");
    outtextxy(300,150,"4");
    outtextxy(170,190,"5");
    outtextxy(345,205,"6");
    outtextxy(440,250,"7");
    outtextxy(250,290,"8");
    outtextxy(150,310,"9");
    outtextxy(350,310,"10");
    outtextxy(450,310,"11");

    setcolor(2);
    outtextxy(500,70,"0-Hospital");
    outtextxy(500,90,"1-Station ");
    outtextxy(500,110,"2-Museum");
    outtextxy(500,130,"3-Government");
    outtextxy(500,150,"4-Park");
    outtextxy(500,170,"5-Shopping Centre");
    outtextxy(500,190,"6-University");
    outtextxy(500,210,"7-Fire Station");
    outtextxy(500,230,"8-Police Station");
    outtextxy(500,250,"9-Aerodrome");
    outtextxy(500,270,"10-Dock");
    outtextxy(500,290,"11-Chemical Plant");

    setfillstyle(1,8);
    bar(330,420,400,450);
    bar(420,420,490,450);
    bar(510,420,580,450);
    setcolor(11);
    outtextxy(50,370,"Please choose the operation: s--Search r--Renew e--Exit");
    setcolor(15);
    outtextxy(340,432,"Search");
    outtextxy(435,432,"Renew");
    outtextxy(528,432,"Exit");
}

/*------點的結構體并初始化--------*/
struct G
{
    int placeName;
    int x;
    int y;     /* 點的坐標及位置名 */
}G[12]={ {0,100,100},{1,100,200},{2,400,150},{3,250,100},{4,300,160},{5,170,200},
          {6,350,200},{7,450,250},{8,250,280},{9,150,300},{10,350,300},{11,450,300}
       };

/*------圖的結構體--------*/
struct graph
{
    struct G G[n];   /* 結點信息 */
    int C[n][n];     /* 邊的權(時間) */
}graphic;

/*-------設置全局變量-------*/
int path[n][n],C[n][n]; /*path[n][n]表示路徑矩陣，C[n][n]表示權值(時間)*/

/*--------建立一個鏈表結構體----*/
struct CellType{
    int num;      /*鏈表中的數*/
    struct CellType *next;/*指向下一個的指針*/
    };

/*--------創建地圖的鄰接矩陣--------*/
Creatgraph()
{
    int i,j;
    struct graph *graphic=NULL;

/*-------對圖的邊進行初始化--------*/
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(i!=j)graphic->C[i][j]=INFINITY;
    for(i=0;i<n;i++)
        graphic->C[i][i]=0;

/*--------給邊的權賦值----------*/
    graphic->C[0][1]=graphic->C[1][0]=4;
    graphic->C[0][3]=graphic->C[3][0]=5;
    graphic->C[0][5]=graphic->C[5][0]=4;
    graphic->C[1][5]=graphic->C[5][1]=3;
    graphic->C[1][3]=graphic->C[3][1]=3;
    graphic->C[1][9]=graphic->C[9][1]=4;
    graphic->C[3][2]=graphic->C[2][3]=4;
    graphic->C[3][4]=graphic->C[4][3]=2;
    graphic->C[5][4]=graphic->C[4][5]=4;
    graphic->C[5][8]=graphic->C[8][5]=2;
    graphic->C[5][9]=graphic->C[9][5]=2;
    graphic->C[9][8]=graphic->C[8][9]=3;
    graphic->C[4][8]=graphic->C[8][4]=3;
    graphic->C[4][2]=graphic->C[2][4]=3;
    graphic->C[4][6]=graphic->C[6][4]=1;
    graphic->C[8][10]=graphic->C[10][8]=6;
    graphic->C[2][6]=graphic->C[6][2]=3;
    graphic->C[2][10]=graphic->C[10][2]=9;
    graphic->C[2][7]=graphic->C[7][2]=4;
    graphic->C[10][11]=graphic->C[11][10]=3;
    graphic->C[7][11]=graphic->C[11][7]=2;
}

/*---------------給出查詢結果路徑--------------*/
struct CellType *head;
struct CellType *p;      /*設一個指向CellType結構體的指針p*/
route(int i,int j)       /*建一個以i為頭指針元素,j為尾的鏈表*/
{
    int k;
    struct CellType *p1;/*設一個指向CellType結構體的指針p1*/
    k=path[i][j];       /*在路徑矩陣中，k為path[i][j]的值*/
    if(k!=0)            /*即i,j之間還有別的點(地點)*/
    {
        route(i,k);     /*遞歸算法*/
        p->num=k;
        p1=p;
        p=(struct CellType *)malloc(LEN);/*為指針p開辟空間*/
        p1->next=p;
        route(k,j);     /*遞歸算法*/
    }
    p->num=j;
    p->next=NULL;
}

/*---------------查詢描繪路徑和節點------------*/
  /*----------  a--起始點 b--終點  -------*/
int a,b;
search(int a,int b)
{

    struct graph *graphic;
    struct CellType *p2;
    struct CellType *p3;

    int suffix1,suffix2,nx1,ny1,nx2,ny2; /*suffix1,suffix2是下標；nx1,ny1,nx2,ny2是坐標*/
    int i,j,k,A[n][n],C[n][n];
    Creatgraph();
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            C[i][j]=graphic->C[i][j];
    for(i=0;i<n;i++)                      /* Floyd算法 */
        for(j=0;j<n;j++) {A[i][j]=C[i][j]; path[i][j]=0;};

    for(k=0;k<n;k++)                     /* A[i][j]（最短路徑矩陣）的初值 */
       for(i=0;i<n;i++)
          for(j=0;j<n;j++)
            if(A[i][k]+A[k][j]<A[i][j])  /*path[i][j]是路徑矩陣*/
               {A[i][j]=A[i][k]+A[k][j];
                 path[i][j]=k;}

    head=(struct CellType *)malloc(LEN);
    head->num=a;
    head->next=NULL;
    p=(struct CellType *)malloc(LEN);
    head->next=p;
    route(a,b);

    p2=p3=head;
    printf("The shortest path from %d to %d is :\n",a,b);
    do
    {   printf("   %d   ",p3->num);
        p3=p3->next;
     }while(p3!=NULL);
    printf("\nThe time spent in the road is %d minutes!",A[a][b]);/*輸出最短路徑長度*/
    p2=head;
    setcolor(4);
   /*---------------著重標出路徑--------------*/
     do
    {
         suffix1=p2->num;
         suffix2=p2->next->num;
         nx1=G[suffix1].x;
         ny1=G[suffix1].y;
         nx2=G[suffix2].x;
         ny2=G[suffix2].y;
         line(nx1,ny1,nx2,ny2);
         p2=p2->next;
    }while(p2->next!=NULL);
   /*---------------著重標出點--------------*/
    setcolor(7);
    setfillstyle(1, 4);
    p2=head;
    do
    {
        suffix1= p2->num;
        nx1=G[suffix1].x;
        ny1=G[suffix1].y;
        p2=p2->next;
        circle(nx1,ny1,3);
        floodfill(nx1,ny1,7);
    }while(p2!=NULL);
    getch();
    main();
    closegraph();
}

/*------------------重新進行使用-------------------*/
renew()
{
    cleardevice();
    menu();
}

/*----------------結束查詢，跳出程序----------------*/
end()
{
    int i;
    int gdriver, gmode;
    gdriver=DETECT;                      /* 屏幕分辨率為640*480 */
    registerbgidriver(EGAVGA_driver);    /* 建立獨立圖形運行程序 */
    initgraph(&gdriver, &gmode, "");
    setcolor(3);
    settextstyle(0,0,8);
    for(i=0;i<=50;i++)
    {
        delay(1000000000000);
        outtextxy(100,200,"Byebye...");
        i++;
    };
    closegraph();
}
checkerror(int e)    /*出錯判斷*/
{
  if( e<0|| e>11 )
                {
                  if(e==-1)
                  {
                   renew();
                   outtextxy(220,390,"Your input is error.Press any key to exit!");
                   getch();
                   end();
                  }
                   outtextxy(220,390,"Your input is error. You must input from 0 to 11!");
                   getch();
                   main();
                }
 }
main()
{
    int check;
    int a=b=-1;
    char c;
    int gdriver, gmode;
    gdriver=DETECT;                      /* 屏幕分辨率為640*480 */
    registerbgidriver(EGAVGA_driver);    /* 建立獨立圖形運行程序 */
    initgraph(&gdriver, &gmode, "");
    menu();
    c=getch();
    while(c!='e')                        /*根據輸入的字符，判斷操作*/
    {
        if(c=='s')
            {
                setcolor(7);
                setfillstyle(1, 4);
                printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");/* 使文本在屏幕左下角輸出 */
                printf("Please enter the locus: ");
                scanf("%d",&a);
                checkerror(a);
                circle(G[a].x,G[a].y,3);
                floodfill(G[a].x,G[a].y,7);

                printf("Please enter the destination:");
                scanf("%d",&b);
                checkerror(b);
                circle(G[b].x,G[b].y,3);
                floodfill(G[b].x,G[b].y,7);

                getch();
                search(a,b);
                exit(0);
            }
        else if(c=='r')
                renew();
        else
            {   setcolor(15);
                outtextxy(220,390,"Your input is error.Renew it then input again!");
            }
        c=getch();
    }
    end();

}