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

79愛的鼓勵 1訂閱站台

作法:DP (有點像是Floyd-Warshall)

來源取自:JoyBO大大所編寫的 連結

題目說明：
給你n個城市的無向圖，請輸出起始點(start)到目的點(end)之間距離不超過len的走法有幾種。

心得：原本用DFS可是會TLE，最後找出DP的規則，假設要從城市A→城市B，就開始建表，先找到是否有城市C→城市B，那在把城市A連結(城市C→城市B)，這樣就從距離1變成距離2，最後再把所有的距離1~len的走法加總起來就是答案。

在此提供 AC的DP(第1) 跟 TLE的DFS(第2)

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

#include<stdio.h>  
#include<stdlib.h>  
int map[33][33]={0};  
int m,k,a,b,c,start,end,N;  
main()  
{  
 while(scanf("%d",&m)==1)  
  {  
   char x[50];  
   int DP[52][33][33]={0};  
   for(a=0;a<m;a++)  
    {  
      scanf("%s",x);  
      for(b=0;b<m;b++)  
       {  
         map[a][b]=x[b]-48;   
         DP[1][a][b]=x[b]-48;  
       }  
    }   
    scanf("%d %d %d",&start,&end,&N);   
    start--;end--;  
    for(k=1;k<=N;k++)  
       for(a=0;a<m;a++)  
          for(b=0;b<m;b++)  
             for(c=0;c<m;c++)  
                if(map[a][c]==1)   /*如果A跟C有相連 則將C →B 的走法加上去 變成C →B →A 就會變成 K 步*/ 
                    DP[k][a][b]=DP[k][a][b]+DP[k-1][c][b];  
    int ans=0;  
    for(a=1;a<=N;a++)  
       ans+=DP[a][start][end];  
    printf("%d\n",ans);   
  }   
 return 0;  
}

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

/**********************************************************************************/
/*  Problem: b062 "1. 城市道路連通網" from 94全國資訊學科能力決賽*/
/*  Language: C                                                                   */
/*  Result: WA (line:4) on ZeroJudge                                              */
/*  Author: morris1028 at 2009-07-16 14:33:30                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
int map[33][33]={0};
int m,a,b,c,ans,start,end,N;
void DFS(int now,int walk)
{
 if(walk>N) return;
 else
   {
     int a;
     if(now==end) {ans++;}
     for(a=1;a<=m;a++)
      if(map[now][a]==1)
       DFS(a,walk+1);
   }
}
main()
{
 while(scanf("%d",&m)==1)
  {
   char x[50];
   for(a=1;a<=m;a++)
    {
      scanf("%s",x);
      for(b=0;b<m;b++)
       map[a][b+1]=x[b]-48;
    }
    ans=0;
    scanf("%d %d %d",&start,&end,&N);
    if(m>20) break;
    DFS(start,0);
    printf("%d\n",ans);
  }
 return 0;
}