摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

/********************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int map[101][50]={0},flag[101]={0},min=2147483647,maptop[101]={0};
int way[101]={0};
int minway[101]={0};
void DFS(int now,int time,int end)
{
  int a,b;
  if(time<min&&now==end)
     {
       min=time; 
       for(a=0;a<=min;a++)
         minway[a]=way[a];         /*將最佳的路徑記錄*/
       return;
     }
  if(now==end||time>=min) return;  /*達到目的地 或者是 已經不可能為最短路徑 則退回*/
  for(a=0;a<maptop[now];a++)
   if(flag[map[now][a]]==0)
    {
      flag[map[now][a]]=1;
      way[time+1]=map[now][a];     /*暫存路徑走法*/
      DFS(map[now][a],time+1,end);
      way[time+1]=0;
      flag[map[now][a]]=0;
    }
}
main()
{
 int n,t,mm;
 scanf("%d",&t);
 while(t--)
   {
     scanf("%d %d",&n,&mm);
     int a,b,c,top=0;
     char xx[101],yy[101],name[101][50]={0},fname[101];
     while(n--)
      {
        scanf("%s %s",xx,yy);
        int m=strlen(xx),flagx,flagy,x[50]={0},y[50]={0};
        /*手動分析字串 幫城市標上號碼*/
        for(a=0;a<m;a++) x[a]=xx[a];
        for(b=0;b<top;b++)
         {
           for(a=0;a<50;a++)
            if(x[a]!=name[b][a]) break;
           if(a==50) {flagx=b;break;}
         }
        if(b==top)
         {
           for(a=0;a<m;a++)
            name[top][a]=x[a];
           flagx=top;top++;
         }
        fname[flagx]=x[0];/*存頭的字母*/
        m=strlen(yy);
        for(a=0;a<m;a++) y[a]=yy[a];
        for(b=0;b<top;b++)
         {
           for(a=0;a<50;a++)
            if(y[a]!=name[b][a]) break;
           if(a==50) {flagy=b;break;}
         }
        if(b==top)
         {
           for(a=0;a<m;a++)
            name[top][a]=y[a];
           flagy=top;top++; 
         }
         fname[flagy]=y[0]; /*存頭的字母*/
         map[flagx][maptop[flagx]]=flagy;/*相鄰矩陣*/
         maptop[flagx]++;
         map[flagy][maptop[flagy]]=flagx;
         maptop[flagy]++; 
      }
      while(mm--)
        {
        scanf("%s %s",xx,yy);
        int m=strlen(xx),flagx,flagy,x[50]={0},y[50]={0};
        /*手動分析字串 找出他們的號碼*/
        for(a=0;a<m;a++) x[a]=xx[a];
        for(b=0;b<top;b++)
         {
           for(a=0;a<50;a++)
            if(x[a]!=name[b][a]) break;
           if(a==50) {flagx=b;break;}
         }
        m=strlen(yy);
        for(a=0;a<m;a++) y[a]=yy[a];
        for(b=0;b<top;b++)
         {
           for(a=0;a<50;a++)
            if(y[a]!=name[b][a]) break;
           if(a==50) {flagy=b;break;}
         }
         min=2147483647;
         flag[flagx]=1;
         DFS(flagx,0,flagy);
         flag[flagx]=0;
         printf("%c",fname[flagx]);
         for(a=1;a<=min;a++)
          printf("%c",fname[minway[a]]);
          printf("\n");
        }
      for(a=0;a<=top;a++)  maptop[a]=0;
   }
 return 0;
}