1178.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 

#include <stdio.h>
#include <math.h>
#include <stdlib.h>


int dis[8][8][8][8];

void floyd()
{
    int i1, i2, i3, j1, j2, j3, t;
    
    for( i1=0; i1<8; i1++ )
    for( j1=0; j1<8; j1++ )
    for( i2=0; i2<8; i2++ )
    for( j2=0; j2<8; j2++ )
    for( i3=0; i3<8; i3++ )
    for( j3=0; j3<8; j3++ )
    	if( ( t = dis[i2][j2][i1][j1] + dis[i1][j1][i3][j3] ) < dis[i2][j2][i3][j3] )
    		dis[i2][j2][i3][j3] = t;
}

int x[64],y[64], n;

void init()
{
    char w[200];
    int i,i1,i2,j1,j2;
    
	scanf( "%s", w );
	
	for( i=0; w[i]; i+= 2 )
		x[i/2] = w[i] - 'A', y[i/2] = w[i+1] - '1';
	
 	n = i / 2;
		
	for( i1=0; i1<8; i1++ )
    for( j1=0; j1<8; j1++ )
    for( i2=0; i2<8; i2++ )
    for( j2=0; j2<8; j2++ )
    	if( ( abs( i1 - i2 ) == 2 && abs( j1 - j2 ) == 1  ) || ( abs( i1 - i2 ) == 1 && abs( j1 - j2 ) == 2 ) )
     		dis[i1][j1][i2][j2] = 1;
       	else if( i1 == i2 && j1 == j2 ) dis[i1][j1][i2][j2] = 0;
        else dis[i1][j1][i2][j2] = 999; 
	
 	floyd();
}

void doit()
{
    int i1, i2, j1, j2, k, ans, t, temp, h;	
    
    ans = 99999;
    for( i1=0; i1<8; i1++ )
    for( j1=0; j1<8; j1++ )
    {
        temp = 0;
        for( k=1; k<n; k++ )
        	temp += dis[x[k]][y[k]][i1][j1];
    	
    	for( k=1; k<n; k++ )
    	{
    	    t = temp - dis[x[k]][y[k]][i1][j1];
    	    
    	    for( i2=0; i2<8; i2++ )
    		for( j2=0; j2<8; j2++ )
    		{
          		h = t + dis[x[k]][y[k]][i2][j2] + dis[i2][j2][i1][j1] + 
            		 ( abs( x[0]-i2 ) > abs( y[0]-j2 ) ? abs( x[0]-i2 ) : abs( y[0]-j2 ) );
            	
             	if( h < ans ) ans = h;
         	}
         	
      	}
   	}
    
    printf( "%d\n", ans );
}

int main()
{
    init();
    doit();
    return 0;
}