二維最短路徑

a3218290

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

1. #include<iostream>
   
2. #include<fstream>
   
3. 
   
4. using namespace std ;
   
5. 
   
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. }

複製代碼