種子論壇 | 高雄市資訊培育協會學員討論區

#include<stdio.h>
#include<stdlib.h>
const int N = 5 ;
const int M = 999 ;
int map[5][5] ;
int hello[25][25] ;
int main()
{
int start,end ;
for(int i=0 ; i < 5 ;i++)
{ for(int j=0 ; j < 5 ;j++)
{
char a[2] ;
scanf("%s",a) ;
if(a[0]=='.')map[i][j]= 1 ;
if(a[0]=='x')map[i][j]= 0 ;
if(a[0]=='s')
{
map[i][j] = 1 ;
start = i*5 + j ;
}
if(a[0]=='e')
{
map[i][j] = 1 ;
end = i*5 + j ;
}
}
}
for(int i=0 ;i<25 ;i++)
{
for(int j=0;j<25;j++)
{
if( ((i>?j) - (i <? j) == 1 || (i>?j) - (i<?j)== 5) && map[i/5][i%5]==1 && map[j/5][j%5]==1)
{
hello[i][j] = 1 ;
hello[j][i] = 1 ;
}else
{
hello [i][j] = M ;
hello [j][i] = M ;
}
}
}
/*for(int i=0 ;i<25 ;i++)
{
for(int j=0;j<25;j++)
{
printf("%d ",hello[i][j]) ;
}
printf("\n") ;
}*/
int parent[25] ;
bool visit[25] ;
int dis[25] ;
for( int i = 0 ; i < 25 ; i ++ )
{
visit[i] = false ;
dis[i] = M ;
}
parent[start] = start ;
dis[start] = 0 ;
for(int i = 0 ; i< 25 ;i++)
{
int min = M+1 , point = -1 ;
for(int j=0 ; j < 25 ;j++)
{
if(visit[j] != true && dis[j] < min)
{
point = j ;
min = dis[j] ;
}
}
//printf("%d %d\n",point, visit[point]) ;
//if(point == -1) break ;
visit[point] = 1 ;
for(int j=0 ; j< 25 ;j++)
{
if(!visit[j] && (dis[j] > dis[point]+hello[point][j]) )
{
dis[j] = dis[point]+hello[point][j] ;
parent[j] = point ;
}
}
}
printf("%d %d",start,end) ;
int val = end ;
printf( "\nstart : %d , end : %d , fee : %d , path : %d " , start , end , dis[end] , end ) ;
while( val != parent[val] )
{
printf( "-> %d" , parent[val] ) ;
val = parent[val] ;
}
scanf (" ") ;
}

複製代碼

#include<iostream>
#include<fstream>
using namespace std ;
const int M = 9999 ; // far way
int main()
{
ifstream fin("pb.in") ;
int p,v,start,end ; // 寬度,總點數,起始點編號,終點編號
p = 5 ;
v = p*p ; // 題目給的 5x5的diagram
int map[v][v] ;
int parent[v] ;
int visit[v] ;
int d[v] ;
// init map and draw map
for( int i = 0 ; i < v ; i ++ )
{
for( int j = 0 ; j < v ; j ++ )
{
map[i][j] = M ;
}
visit[i] = false ;
d[i] = M ;
}
// read pb.in diagram
for( int i = 0 ; i < v ; i ++ )
{
string x ;
fin >> x ;
if( x == "e" ) end = i ;
if( x == "s" ) start = i ;
if( x == "x" ) visit[i] = true ;
}
// check diagram
for( int i = 0 ; i < v ; i ++ )
{
if( i%p != p-1 && !visit[i+1] )
{
map[i][i+1] = 1 ;
map[i+1][i] = 1 ;
}
if( i%p != 0 && !visit[i-1] )
{
map[i][i-1] = 1 ;
map[i-1][i] = 1 ;
}
if( i >= p && !visit[i-p] )
{
map[i][i-p] = 1 ;
map[i-p][i] = 1 ;
}
if( i < (p-1)*p && !visit[i+p] )
{
map[i][i+p] = 1 ;
map[i+p][i] = 1 ;
}
}
/* for( int i = 0 ; i < v ; i ++ )
{
for( int j = 0 ; j < v ; j ++ )
{
cout << map[i][j] << " " ;
}
cout << endl ;
}
cout << start << "-" << end << endl ; */
// dijkstra
d[start] = 0 ;
parent[start] = start ;
for( int i = 0 ; i < v ; i ++ )
{
int min = M ;
int index = -1 ;
for( int j = 0 ; j < v ; j ++ )
{
if( !visit[j] && d[j] < min )
{
min = d[j] ;
index = j ;
}
}
if( index == -1 ) break ;
visit[index] = true ;
for( int j = 0 ; j < v ; j ++ )
{
if( !visit[j] && ( d[index] + map[index][j] < d[j] ) )
{
d[j] = d[index] + map[index][j] ;
parent[j] = index ;
}
}
}
/* for( int i = 0 ; i < v ; i ++ )
{
cout << d[i] << " " ;
}
cout << endl ; */
//for( int i = 0 ; i < v ; i ++ )
//{
int pre = end ;
cout << pre << "->" ;
while( parent[pre] != pre )
{
pre = parent[pre] ;
cout << pre << "->" ;
}
cout << "cost" << d[end] << endl ;
//}
system("Pause") ;
}

複製代碼