二維最短路徑

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. }

複製代碼