Poj Solution 1178

http://poj.org/problem?id=1178

//* @author: 
import java.util.*;
public class Main {

static int dis[][][][]=new int[8][8][8][8];
static int x[]=new int[64],y[]=new int[64], n;

static 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;
}


static void init()
{
    char w[]=new char[200];
    int i,i1,i2,j1,j2;
    Scanner in = new Scanner(System.in);
     w=in.next().toCharArray();
    
    for( i=0; i< w.length-1; 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( ( Math.abs( i1 - i2 ) == 2 && Math.abs( j1 - j2 ) == 1  ) || ( Math.abs( i1 - i2 ) == 1 && Math.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();
}

static 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] + 
           ( Math.abs( x[0]-i2 ) > Math.abs( y[0]-j2 ) ? Math.abs( x[0]-i2 ) : Math.abs( y[0]-j2 ) );
                
           if( h < ans ) ans = h;
          }
             
          }
       }
    
    System.out.printf( "%dn", ans );
}

 public static void main(String[] args){

    init();
    doit();
 }               
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *