Board logo

標題: 二維最短路徑 [打印本頁]

作者: a3218290    時間: 2011-9-10 21:36     標題: 二維最短路徑

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. const int N = 5 ;
  4. const int M = 999 ;
  5. int map[5][5] ;
  6. int hello[25][25] ;
  7. int main()
  8. {
  9.     int start,end ;
  10.     for(int i=0 ; i < 5 ;i++)
  11.     {    for(int j=0 ; j < 5 ;j++)
  12.         {
  13.             char a[2] ;
  14.             scanf("%s",a) ;
  15.             if(a[0]=='.')map[i][j]= 1 ;
  16.             if(a[0]=='x')map[i][j]= 0 ;
  17.             if(a[0]=='s')
  18.             {
  19.                 map[i][j] = 1 ;
  20.                 start = i*5 + j ;   
  21.             }
  22.             if(a[0]=='e')
  23.             {
  24.                 map[i][j] = 1 ;
  25.                 end = i*5 + j ;   
  26.             }
  27.         }
  28.     }
  29.     for(int i=0 ;i<25 ;i++)
  30.     {
  31.         for(int j=0;j<25;j++)
  32.         {
  33.             if( ((i>?j) - (i <? j) == 1 || (i>?j) - (i<?j)== 5) && map[i/5][i%5]==1 && map[j/5][j%5]==1)
  34.             {
  35.                 hello[i][j] = 1 ;
  36.                 hello[j][i] = 1 ;   
  37.             }else
  38.             {
  39.                 hello [i][j] = M ;
  40.                 hello [j][i] = M ;   
  41.             }   
  42.         }
  43.     }
  44.     /*for(int i=0 ;i<25 ;i++)
  45.     {
  46.         for(int j=0;j<25;j++)
  47.         {
  48.             printf("%d ",hello[i][j]) ;   
  49.         }
  50.         printf("\n") ;
  51.     }*/
  52.    
  53.     int parent[25] ;
  54.     bool visit[25] ;
  55.     int dis[25] ;
  56.     for( int i = 0 ; i < 25 ; i ++ )
  57.     {
  58.         visit[i] = false ;
  59.         dis[i] = M ;     
  60.     }
  61.     parent[start] = start ;
  62.     dis[start] = 0 ;
  63.    
  64.     for(int i = 0 ; i< 25 ;i++)
  65.     {
  66.         int min = M+1 , point = -1 ;
  67.         for(int j=0 ; j < 25 ;j++)
  68.         {
  69.            if(visit[j] != true && dis[j] < min)
  70.            {
  71.                 point = j ;
  72.                 min = dis[j] ;   
  73.            }   
  74.         }
  75.          
  76.         //printf("%d %d\n",point, visit[point]) ;
  77.         //if(point == -1) break ;
  78.         visit[point] = 1 ;
  79.         for(int j=0 ; j< 25 ;j++)
  80.         {
  81.             if(!visit[j] && (dis[j] > dis[point]+hello[point][j]) )
  82.             {
  83.                 dis[j] = dis[point]+hello[point][j] ;
  84.                 parent[j] = point ;
  85.             }   
  86.         }   
  87.     }
  88.     printf("%d %d",start,end) ;
  89.     int val = end ;
  90.     printf( "\nstart : %d , end : %d , fee : %d , path : %d " , start , end , dis[end] , end ) ;
  91.     while( val != parent[val] )
  92.     {
  93.             printf( "-> %d" , parent[val] ) ;
  94.             val = parent[val] ;
  95.     }
  96.    
  97.    
  98.    
  99.     scanf (" ") ;
  100. }
複製代碼

作者: Alen    時間: 2011-9-10 21:40

  1. #include<iostream>
  2. #include<fstream>

  3. using namespace std ;

  4. const int M = 9999 ; // far way
  5.    
  6. int main()
  7. {
  8.     ifstream fin("pb.in") ;
  9.    
  10.     int p,v,start,end ; // 寬度,總點數,起始點編號,終點編號
  11.     p = 5 ;
  12.     v = p*p ; // 題目給的 5x5的diagram
  13.     int map[v][v] ;
  14.     int parent[v] ;
  15.     int visit[v] ;
  16.     int d[v] ;   
  17.     // init map and draw map
  18.     for( int i = 0 ; i < v ; i ++ )
  19.     {
  20.         for( int j = 0 ; j < v ; j ++ )     
  21.         {
  22.             map[i][j] = M ;     
  23.         }
  24.         visit[i] = false ;
  25.         d[i] = M ;
  26.     }   
  27.     // read pb.in diagram            
  28.     for( int i = 0 ; i < v ; i ++ )
  29.     {
  30.         string x ;
  31.         fin >> x ;
  32.         if( x == "e" ) end = i ;
  33.         if( x == "s" ) start = i ;                     
  34.         if( x == "x" ) visit[i] = true ;
  35.     }   
  36.      
  37.     // check diagram
  38.     for( int i = 0 ; i < v ; i ++ )
  39.     {
  40.         if( i%p != p-1 && !visit[i+1] )
  41.         {
  42.             map[i][i+1] = 1 ;
  43.             map[i+1][i] = 1 ;   
  44.         }
  45.         if( i%p != 0 && !visit[i-1] )
  46.         {
  47.             map[i][i-1] = 1 ;
  48.             map[i-1][i] = 1 ;   
  49.         }
  50.         if( i >= p && !visit[i-p] )            
  51.         {
  52.             map[i][i-p] = 1 ;
  53.             map[i-p][i] = 1 ;   
  54.         }
  55.         if( i < (p-1)*p && !visit[i+p] )
  56.         {
  57.             map[i][i+p] = 1 ;
  58.             map[i+p][i] = 1 ;
  59.         }  
  60.     }
  61.    
  62. /*    for( int i = 0 ; i < v ; i ++ )
  63.     {
  64.         for( int j = 0 ; j < v ; j ++ )     
  65.         {
  66.             cout << map[i][j] << " " ;     
  67.         }
  68.         cout << endl ;
  69.     }
  70.     cout << start << "-" << end << endl ;  */
  71.                      
  72.     // dijkstra
  73.     d[start] = 0 ;
  74.     parent[start] = start ;
  75.     for( int i = 0 ; i < v ; i ++ )
  76.     {
  77.          int min = M ;
  78.          int index = -1 ;
  79.          for( int j = 0 ; j < v ; j ++ )
  80.          {
  81.              if( !visit[j] && d[j] < min )
  82.              {
  83.                  min = d[j] ;
  84.                  index = j ;
  85.              }     
  86.          }
  87.          
  88.          if( index == -1 ) break ;
  89.          visit[index] = true ;
  90.          for( int j = 0 ; j < v ; j ++ )
  91.          {
  92.              if( !visit[j] && ( d[index] + map[index][j] < d[j] ) )     
  93.              {
  94.                  d[j] = d[index] + map[index][j] ;
  95.                  parent[j] = index ;                    
  96.    
  97.              }
  98.          }   
  99.     }
  100. /*    for( int i = 0 ; i < v ; i ++ )
  101.     {
  102.         cout << d[i] << " " ;
  103.     }
  104.     cout << endl ; */
  105.     //for( int i = 0 ; i < v ; i ++ )
  106.     //{
  107.         int pre = end ;           
  108.         cout << pre << "->" ;         
  109.         while( parent[pre] != pre )
  110.         {
  111.            pre = parent[pre] ;
  112.            cout << pre << "->" ;
  113.         }
  114.         cout << "cost" << d[end] << endl ;
  115.     //}
  116.      
  117.    
  118.     system("Pause") ;
  119. }
複製代碼





歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2