返回列表 發帖

Rank: 1
1# 跳轉到 » 倒序看帖
打印
tT
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. }
複製代碼
收藏 分享

Rank: 1
2#
Alen發表於 2011-9-10 21:40 | 只看該作者
  1. #include<iostream>
  2. #include<fstream>

  4. using namespace std ;

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

                                ..士豪(Alen)黑輪

TOP

返回列表