/*  POTM ENTRY:  spider */
/*  Your Name:   Alexei Garianov */
/*  Your email:  al.garry@worldnet.att.net */
/* */
/*  version 1.8  */
/*  date: June 24, 1998 */


#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>

/* #define SP_ASSERT */
/* #define SP_DEB_OUTPUT */
/* #define SP_DEB_WAIT */

/* definitions of data structures */
typedef struct Path_xxx
{
 unsigned int*  m_array;
 int   m_num;
    int   m_wei;
    int   m_val;

 int*  m_map;
 int   m_free;
} Path;

typedef struct Path_xxx_yyy
{
 Path**  m_arr;
 int     m_num;
    int     m_size;

} PathList;

/* definitions of functions */
void inittime();
int  checktime(); /* 0 when time is over */

void  main_on_short( Path* a_short_path );

PathList*  pl_create();
void       pl_destroy( PathList* a_path_list );
void       pl_add( PathList* a_path_list, Path* a_path );
void       pl_del( PathList* a_path_list, int a_pos );

void  sp_find_all_short_one( PathList*  a_list,
        Path*  a_bck_path,
        int    a_max_len,
        int    a_dir );

void  sp_store_short_one( Path* a_path, 
        PathList*  a_list );
int   sp_read_data_file( const char* a_file_name );
void  sp_create_naib();
void  sp_init_queue();
void  sp_free_resources();
void  sp_free_queue();
void  sp_expand_queue();

Path* sp_create_path();
Path* sp_clone_path( Path* a_path );
void  sp_free_path( Path* a_path );
Path* sp_find_free_path();
Path* sp_inverte_path( Path* a_path );
void  sp_add_point( Path* a_path, int a_pos, 
        int a_point );
void  sp_append_point( Path* a_path, 
        unsigned int a_point );
void  sp_calc_path_wei( Path* a_path );
void  sp_set_bk_path( Path* a_path );
void  sp_start_short_path_search( int a_from, 
          int a_to, 
          int a_max_num );
Path* sp_find_short_path();  

void  sp_start_long_path_search( int a_from, 
        int a_to, int a_max_num );
Path* sp_find_long_path();  

void sp_on_ready_path( Path* a_short_path, 
        Path* a_long_path );
void sp_print_best_path();

Path* sp_find_best_long_path( int a_max_len, 
         Path* a_bck_path );
void  sp_grow_point( Path* a_long_path, 
      Path* a_short_path );

/* utility functions */
int  sp_read_data_file( const char* a_file_name );
int  sp_is_neib( int a_p1, int a_p2 );
int  sp_calc_wei( int a_p1, int a_p2 );
int  sp_calc_min_dist( int p1, int p2 );
void sp_rem_path_from_queue( int a_pos );
void sp_insert_path_in_queue( int a_pos, Path* a_path );
void sp_rem_pathes_on_point( int a_point );

void sp_push_short_path_in_queue( Path* a_path );
int  sp_extend_short_path( Path* a_path, 
         Path* a_ext_pathes[ 8 ] );

void sp_push_long_path_in_queue( Path* a_path );
int  sp_find_ins_point( int a_val );
int  sp_find_ins_point_short( int a_val );

int  sp_extend_long_path( Path* a_path, 
        Path* a_ext_pathes[ 8 ] );
/* macros */

#define SP_IND_2_X( i ) ( ( i ) % glb_w )
#define SP_IND_2_Y( i ) ( ( i ) / glb_w )
#define SP_XY_2_IND( x, y ) ( ( ( y ) *  glb_w ) + ( x ) )

#define SP_IS_XY_GOOD( x, y ) \
    ( ( ( x ) >= 0 ) && ( ( x ) < glb_w ) && \
      ( ( y ) >= 0 ) && ( ( y ) < glb_h ) )

#define SP_GET_NEIB( x ) ( ( ( x ) * 9 ) + glb_naib )

#define SP_EVAL_LONG( wei, num ) \
 ( ( wei ) + ( ( glb_long_k1 * ( wei ) \
    * glb_search_num ) / ( num ) ) )

#define SP_EVAL_SHORT( wei, num, head ) \
 ( ( wei ) + ( ( num ) * glb_short_k1 ) )

#define SP_IS_POINT_ON_PATH( path, pnt ) \
 ( ( path )->m_map[ ( pnt ) >> 5 ] & \
 glb_masks[ ( pnt ) & 0x1F ] )

#define SP_REM_PATHES( a_point )\
 sp_rem_pathes_on_point( a_point )

#ifdef SP_ASSERT
#define SP_TEST_PATH( x ) sp_test_path( x );
#else
#define SP_TEST_PATH( x ) 
#endif

#ifdef SP_ASSERT
#define SP_BREAK  ( gav_one / gav_zero )
#else
#define SP_BREAK  
#endif

int gav_one = 1;
int gav_zero = 0;

/* search queue */
Path**  glb_queue_arr = 0;
int     glb_queue_len = 0;
int     glb_queue_size = 0;
int*    glb_best_vals = 0;

unsigned int  glb_search_beg = 0;
unsigned int  glb_search_end = 0;
int     glb_search_num = 0;
Path*   glb_bck_path = 0;

int*    glb_used_map = 0;

int     glb_short_k1 = 1;
int     glb_long_k1 = 2;

Path*   glb_best_path = 0;
double  glb_best_k = 0;

/* problem data */
unsigned int  glb_path_beg = 0;
unsigned int  glb_path_end = 0;
int  glb_path_max_len = 0;
int  glb_w = 0;
int  glb_h = 0;
int  glb_max_alt = 0;
int* glb_map = 0;
int  glb_map_size = 0;
int* glb_naib = 0;

/* "is point on path" stuff */
int  glb_path_map_size = 0;
int  glb_masks[ 32 ];

/* memory handling variables */
#define FR_ST_SIZE 200

PathList* glb_path_pool = 0;
int  glb_free_path_num = 0;
Path* glb_free_stack[ FR_ST_SIZE + 10 ];
int  glb_free_stack_ptr = 0;

/***********************************************/
int  sp_read_data_file( const char* a_file_name )
{
    int sc = 0;
    int i=0;
 FILE* file = fopen( a_file_name, "rt" );
 if( file == 0 )
  return 0;

 sc = fscanf( file, "P2\n# %i\n%i %i\n%i",
      &glb_path_max_len,
      &glb_w, &glb_h, &glb_max_alt );

 if( sc != 4 )
 {
  fclose( file );
  return 0;
 }

 glb_map_size = glb_w * glb_h ;
 glb_map = ( int* )malloc( sizeof(int)* glb_map_size );
 if( glb_map == 0 )
 {
  fclose( file );
  return 0;
 }

 for( i=0; i<glb_map_size; i++ )
  fscanf( file, "%i", glb_map + i );

 sp_create_naib();

 glb_used_map = ( int* )calloc( glb_map_size, 
         sizeof( int ) );

 fclose( file );
 return 1;
}

/***********************************************/
void sp_create_naib()
{
    signed int offsets[ 8 ][ 2 ] = {
  {-1,-1},
  {1,-1},
  {1,1},
  {-1,1},
  {0,-1},
  {1,0},
  {0,1},
  {-1,0} };

    signed int y=0; 
    signed int x=0; 
    signed int i=0; 

    glb_naib = ( int* )malloc( sizeof( int ) 
        * 9 * glb_map_size );
    for( y=0; y<glb_h; y++ )
    {
        for( x=0; x<glb_w; x++ )
        {
            int point = SP_XY_2_IND( x, y );
            int neib_pos = ( point * 9 );

            for( i=0; i<8; i++ ) 
            {
                int xx = x + offsets[ i ][ 0 ];
                int yy = y + offsets[ i ][ 1 ];
                if( SP_IS_XY_GOOD( xx, yy ) )
                {
                    int ind = SP_XY_2_IND( xx, yy );
                    glb_naib[ neib_pos++ ] = ind;
                }
            }

            glb_naib[ neib_pos++ ] = point;
        }
    }
}

/***********************************************/
void sp_init_queue()
{
 sp_free_queue();
 glb_queue_size = 1000;
 glb_queue_arr = ( Path** )malloc( glb_queue_size 
         * sizeof( Path* ) );
 glb_best_vals = ( int* )calloc( glb_map_size, 
         sizeof( int ) );
}

/***********************************************/
void sp_free_queue()
{
 if( glb_queue_size )
 {
  int i=0; 
  for( i=0; i<glb_queue_len; i++ )
  {
   sp_free_path( glb_queue_arr[ i ] );
  }

  free( glb_queue_arr );
  free( glb_best_vals );
 }

 glb_queue_len = glb_queue_size = 0;
 glb_queue_arr = 0;
}

/***********************************************/
void sp_free_resources()
{
 int i=0;

 free( glb_map );
 free( glb_naib );
 free( glb_used_map );

 sp_free_queue();

 if( glb_best_path )
 {
  sp_free_path( glb_best_path );
  glb_best_path = 0;
 }

 for( i=0; i<glb_path_pool->m_num; i++ )
 {
  Path* path = glb_path_pool->m_arr[ i ];
  free( path->m_array );
  free( path->m_map );
  free( path );
 }

 free( glb_path_pool->m_arr );
 free( glb_path_pool );
}

/***********************************************/
Path* sp_create_path()
{
 int pnts_size = ( glb_w + glb_path_max_len + 2 )
       * sizeof( int );
 Path* path = sp_find_free_path();

 if( path == 0 )
 {
  glb_free_path_num = 0;

  path = ( Path* )calloc( sizeof( Path ), 1 );
  path->m_array = ( int* )malloc( sizeof( int ) 
       * ( glb_path_max_len + 1 ) );
  path->m_map = ( int* )calloc( glb_path_map_size, 
          sizeof( int ) );

  pl_add( glb_path_pool, path );
 }
 else
 {
  memset( path->m_map, 0, 
    glb_path_map_size * sizeof( int ) );
 }

 path->m_free = 0;
 return path;
}

/***********************************************/
Path* sp_find_free_path()
{
 Path* path;
 int i;
 Path** arr;
 int num;

 if( glb_free_stack_ptr )
 {
  path = glb_free_stack[ --glb_free_stack_ptr ];
  return path;
 }

 if( !glb_free_path_num )
  return 0;

 path = 0;
 i=0;
 arr = glb_path_pool->m_arr;
 num = glb_path_pool->m_num;

 for( i=0; i<num; i++ )
 {
  if( arr[ i ]->m_free )
  {
   glb_free_path_num--;
   path = arr[ i ];
   break;
  }
 }

 return path;
}

/***********************************************/
Path* sp_clone_path( Path* a_path )
{
 int pnts_size = ( glb_w + glb_path_max_len + 2 ) 
       * sizeof( int );

 Path* path = sp_find_free_path();

 if( path == 0 )
 {
  glb_free_path_num = 0;
  path = ( Path* )calloc( sizeof( Path ), 1 );
  path->m_array = ( int* )malloc( sizeof( int ) 
      * ( glb_path_max_len + 1 ) );
  path->m_map = ( int* )malloc( glb_path_map_size 
         * sizeof( int ) );
  pl_add( glb_path_pool, path );
 }

 path->m_free = 0;
 path->m_num = a_path->m_num;
    path->m_wei = a_path->m_wei;
    path->m_val = a_path->m_val;

 memcpy( path->m_array, 
   a_path->m_array, 
   a_path->m_num * sizeof( int ) );

 memcpy( path->m_map, a_path->m_map, 
    glb_path_map_size * sizeof( int ) );
 
 return path;
}

/***********************************************/
void  sp_free_path( Path* a_path )
{
 glb_free_path_num++;

 a_path->m_num = 0;
    a_path->m_wei = 0;
    a_path->m_val = 0;
 a_path->m_free = 1;

 if( glb_free_stack_ptr < FR_ST_SIZE )
  glb_free_stack[ glb_free_stack_ptr++ ] = a_path;
}

/***********************************************/
void  sp_start_short_path_search( int a_from, 
         int a_to, int a_max_num )
{
 Path* path = 0;

 glb_search_beg = a_from;
 glb_search_end = a_to;
 glb_search_num = a_max_num;

    sp_init_queue();
 path = sp_create_path();

 sp_append_point( path, a_from );
 sp_push_short_path_in_queue( path );
}

/***********************************************/
void  sp_rem_path_from_queue( int a_pos )
{
 int to_move = glb_queue_len - a_pos - 1;
 sp_free_path( glb_queue_arr[ a_pos ] );

 if( to_move )
 {
  memmove( glb_queue_arr + a_pos, 
     glb_queue_arr + a_pos + 1,
     to_move * sizeof( Path* ) );
 }

 glb_queue_len--;
}

/***********************************************/
void  sp_insert_path_in_queue( int a_pos, Path* a_path )
{
 int to_move = glb_queue_len - a_pos;
 if( glb_queue_len >= glb_queue_size )
  sp_expand_queue();

 if( to_move )
 {
  memmove( glb_queue_arr + a_pos + 1,
     glb_queue_arr + a_pos,
        to_move * sizeof( Path* ) );
 }

 glb_queue_arr[ a_pos ] = a_path;
 glb_queue_len++;
}

/***********************************************/
void sp_expand_queue()
{
 int a_size = 0;

 glb_queue_size += 1000;
 a_size = sizeof( Path* ) * glb_queue_size;
 if( glb_queue_arr )
 {
  glb_queue_arr = ( Path**  )
   realloc( glb_queue_arr, a_size );
 }
 else
 {
  glb_queue_arr = ( Path**  )
   malloc( a_size );
 }
}

/***********************************************/
Path* sp_inverte_path( Path* a_path )
{
 int num = a_path->m_num;
 int* arr = a_path->m_array;
 int i=0;
 Path* new_path = sp_create_path();
 for( i=num; i>0; i-- )
 {
  sp_append_point( new_path, arr[ i - 1 ] );
 }

 new_path->m_wei = a_path->m_wei;
 new_path->m_val = a_path->m_val;

 sp_free_path( a_path );
 return new_path;
}

/***********************************************/
int  sp_calc_min_dist( int p1, int p2 )
{
 int x1 = SP_IND_2_X( p1 );
 int y1 = SP_IND_2_Y( p1 );
 int x2 = SP_IND_2_X( p2 );
 int y2 = SP_IND_2_Y( p2 );
 int dx = x2 - x1;
 int dy = y2 - y1;

 if( x1 > x2 )
  dx = x1 - x2;

 if( y1 > y2 )
  dy = y1 - y2;

 if( dx > dy )
  return dx;

 return dy;
}

/***********************************************/
int  sp_is_neib( int a_p1, int a_p2 )
{
 int* ptr = SP_GET_NEIB( a_p1 );
 while( *ptr != a_p1 )
 {
  if( *ptr++ == a_p2 )
   return 1;
 }

 return 0;
}

/***********************************************/
int sp_calc_wei( int a_p1, int a_p2 )
{
 int a1 = glb_map[ a_p1 ];
 int a2 = glb_map[ a_p2 ];
 if( a1 > a2 )
  return ( a1 - a2 );
 else
  return ( a2 - a1 );
}

/***********************************************/
void sp_postprocess_queue()
{
 int  i = 0;
  for( i=0; i<glb_queue_len; i++ )
  {
   Path* path = glb_queue_arr[ i ];
   if( path->m_val > 
    glb_best_vals[ 
     path->m_array[ path->m_num - 1 ] ] )
   {
    sp_rem_path_from_queue( i-- );
   }
  }
}

/***********************************************/
void sp_ext_push_pathe( Path*  a_path )
{
 Path* ext_pathes[ 8 ];
 int  ext_path_num = 0;
 int  i = 0;
 static int  xxx = 0;

 ext_path_num = sp_extend_short_path( a_path, 
           ext_pathes );
 sp_free_path( a_path );

 for( i=0; i<ext_path_num; i++ )
 {
  sp_push_short_path_in_queue( ext_pathes[ i ] );
 }

 xxx = ( xxx++ ) % 3;

 if( xxx == 0 )
  sp_postprocess_queue();
}

/***********************************************/
Path* sp_find_short_path()
{
 while( glb_queue_len && checktime() )
 {
  Path* path = glb_queue_arr[ --glb_queue_len ];
  int head = path->m_array[ path->m_num - 1 ];
  if( sp_is_neib( head, glb_search_end ) )
  {
   path->m_array[path->m_num++] = glb_search_end;
   path->m_wei += 
    sp_calc_wei( head, glb_search_end );
   return path;
  }

  sp_ext_push_pathe( path );
 }

 return 0;
}

/***********************************************/
int  sp_extend_short_path( Path* a_path, 
         Path* a_ext_pathes[ 8 ] )
{
 int head = a_path->m_array[ a_path->m_num - 1 ];
 int* ptr = SP_GET_NEIB( head );
 int ext_num = 0;
 int new_num = a_path->m_num + 1;
 int new_wei = 0;
 int new_val = 0;
 int prev = 0;
 int i=0;
 int num = a_path->m_num;
 int* arr = a_path->m_array;
 if( a_path->m_num > 1 )
  prev = a_path->m_array[ a_path->m_num - 2 ];

 while( *ptr != head )
 {
  int dist = 0;
  Path* new_path = 0;

  int next = *ptr++;

  if( SP_IS_POINT_ON_PATH( a_path, next ) )
   continue;

  if( glb_bck_path && 
   SP_IS_POINT_ON_PATH( glb_bck_path, next ) )
   continue;

  if( !glb_bck_path && ( new_num > 2 ) &&
   ( sp_is_neib( next, prev ) ) )
   continue;

  dist = sp_calc_min_dist( next, glb_search_end );
  if( ( dist + new_num ) > glb_search_num )
   continue;

  
  new_wei = a_path->m_wei + sp_calc_wei( head, next );
  new_val = SP_EVAL_SHORT( new_wei, new_num, next );
  if( ( glb_best_vals[ next ] ) && 
   ( new_val >= glb_best_vals[ next ] ) )
  {
   {
    continue;
   }
  }
  
  /* create new path */
  new_path = sp_clone_path( a_path );

  sp_append_point( new_path, next );

  new_path->m_wei = new_wei;
  new_path->m_val = new_val;

  a_ext_pathes[ ext_num++ ] = new_path;
 }

 return ext_num;
}

/***********************************************/
void  sp_start_long_path_search( int a_from, 
         int a_to, 
         int a_max_num )
{
 Path* path = 0;

 glb_search_beg = a_from;
 glb_search_end = a_to;
 glb_search_num = a_max_num;

    sp_init_queue();
 path = sp_create_path();

 sp_append_point( path, a_from );
 sp_push_long_path_in_queue( path );
}

/***********************************************/
Path* sp_find_long_path()
{
 Path* ext_pathes[ 8 ];
 int  ext_path_num = 0;
 int i=0; 

 while( glb_queue_len && checktime() )
 {
  Path* path = glb_queue_arr[ --glb_queue_len ];
  int head = path->m_array[ path->m_num - 1 ];
  if( sp_is_neib( head, glb_search_end ) )
  {
   path->m_array[path->m_num++] = glb_search_end;
   path->m_wei += 
    sp_calc_wei( head, glb_search_end );
   return path;
  }

  ext_path_num = 
   sp_extend_long_path( path, ext_pathes );
  sp_free_path( path );

  for( i=0; i<ext_path_num; i++ )
  {
   sp_push_long_path_in_queue( ext_pathes[ i ] );
  }
 }

 return 0;
}

/***********************************************/
int  sp_extend_long_path( Path* a_path, 
       Path* a_ext_pathes[ 8 ] )
{
 int head = a_path->m_array[ a_path->m_num - 1 ];
 int* ptr = SP_GET_NEIB( head );
 int ext_num = 0;
 int new_num = a_path->m_num + 1;
 int new_wei = 0;
 int new_val = 0;
 int wei = a_path->m_wei;

 /* expanding */
 while( *ptr != head )
 {
  int dist = 0;
  Path* new_path = 0;

  int next = *ptr++;
  if( SP_IS_POINT_ON_PATH( a_path, next ) )
   continue;

  if( glb_bck_path && 
   SP_IS_POINT_ON_PATH( glb_bck_path, next ) )
   continue;

  dist = sp_calc_min_dist( next, glb_search_end );
  if( ( dist + new_num ) > glb_search_num )
   continue;

  new_wei = wei + sp_calc_wei( head, next );
  new_val = SP_EVAL_LONG( new_wei, new_num );
  if( ( glb_best_vals[ next ] ) &&
   ( new_val < glb_best_vals[ next ] ) )
  {
   continue;
  }

  /* create new path */
  new_path = sp_clone_path( a_path );
  
  sp_append_point( new_path, next );
  new_path->m_wei = new_wei;
  new_path->m_val = new_val;
  a_ext_pathes[ ext_num++ ] = new_path;
 }

 return ext_num;
}

/***********************************************/
void  sp_set_bk_path( Path* a_path )
{
 glb_bck_path = a_path;
}

/***********************************************/
void  sp_calc_path_wei( Path* a_path )
{
 int num = a_path->m_num;
 int w = 0;
 int i = 0; 
 for( i=1; i<num; i++ )
 {
  int p1 = a_path->m_array[ i - 1 ];
  int p2 = a_path->m_array[ i ];
  w += sp_calc_wei( p1, p2 );
 }

 a_path->m_wei = w;
}

/***********************************************/
void sp_on_ready_path( Path* a_short_path, 
       Path* a_long_path )
{
  int i = 0;
 Path* path = 0;
 int num = 0;
 int k = 0;
 int w1 = 0;
 int w2 = 0;
 int flag = 0;
 double kk = 0;
 double kw1 = 0;
 double kw2 = 0;

 int short_num = a_short_path->m_num;
 int long_num = a_long_path->m_num;

 if( a_short_path->m_array[ 0 ] != glb_path_beg )
  SP_BREAK;

 if( a_short_path->m_array[ short_num - 1  ] 
   != glb_path_end )
  SP_BREAK;

 if( a_long_path->m_array[ 0 ] != glb_path_end )
  SP_BREAK;

 if( a_long_path->m_array[ long_num - 1  ] 
   != glb_path_beg )
  SP_BREAK;

 path = sp_create_path();
 for( i=0; i<short_num; i++ )
 {
  path->m_array[ path->m_num++ ] = 
   a_short_path->m_array[ i ];
 }
 
 for( i=1; i<long_num; i++ )
 {
  path->m_array[ path->m_num++ ] = 
   a_long_path->m_array[ i ];
 }

 if( path->m_num > glb_path_max_len + 1 )
  SP_BREAK;

 num = path->m_num;
 for( i=1; i<num; i++ )
 {
  int p1 = path->m_array[ i - 1 ];
  int p2 = path->m_array[ i ];
  if( !sp_is_neib( p1, p2 ) )
  {
   SP_BREAK;
  }

  for( k=i; k < ( num - 1 ); k++ )
  {
   int pk = path->m_array[ k ];
   if( p1 == pk )
   {
    SP_BREAK;
   }
  }
 }

 for( i=1; i<num; i++ )
 {
  unsigned int p1 = path->m_array[ i - 1 ];
  unsigned int p2 = path->m_array[ i ];
  int dw = sp_calc_wei( p1,p2 );

  if( flag == 0 )
   w1 += dw;
  else
   w2 += dw;

  if( p2 == glb_path_end )
   flag = 1;
 }

 kw1 = w1;
 kw2 = w2;
 kk = kw2 / kw1;

#ifdef SP_DEB_OUTPUT
 printf( "full path L=%i K=%f (%i,%i) (%i,%i)\n",
   num - 1, kk, 
   short_num - 1, w1,
   long_num - 1, w2 );
#endif

 if( kk > glb_best_k )
 {
  if( glb_best_path )
  {
   sp_free_path( glb_best_path );
   glb_best_path = 0;
  }

  glb_best_path = path;
  glb_best_k = kk;
 }
 else
 {
  sp_free_path( path );
 }
}

/***********************************************/
Path* sp_find_best_long_path( int a_max_len, 
        Path* a_bck_path ) 
{
 int max_wei = 0;
 int max_len = 0;
 Path* best_long_path = 0;
 Path* path = 0;
 sp_set_bk_path( a_bck_path );

 sp_start_long_path_search( glb_path_end, 
          glb_path_beg,
          a_max_len + 1 );

 while( path = sp_find_long_path() )
 {
  SP_TEST_PATH( path );

#ifdef SP_LOCAL_OPT
  sp_enhance_long_path( path );
  SP_TEST_PATH( path );
#endif

  if( path->m_wei > max_wei )
  {
   max_wei = path->m_wei;
   max_len = path->m_num - 1;

   if( best_long_path )
   {
    sp_free_path( best_long_path );
    best_long_path = 0;
   }

   best_long_path = path;
  }
  else
  {
   sp_free_path( path );
  }
 }

 sp_start_long_path_search( glb_path_beg, 
           glb_path_end,
           a_max_len + 1 );

 while( path = sp_find_long_path() )
 {
  SP_TEST_PATH( path );
  path = sp_inverte_path( path );
  SP_TEST_PATH( path );

#ifdef SP_LOCAL_OPT
  sp_enhance_long_path( path );
  SP_TEST_PATH( path );
#endif
  if( path->m_wei > max_wei )
  {
   if( best_long_path )
   {
    sp_free_path( best_long_path );
    best_long_path = 0;
   }

   best_long_path = path;
   max_wei = path->m_wei;
   max_len = path->m_num - 1;
  }
  else
  {
   sp_free_path( path );
  }
 }

 return best_long_path;
}

/***********************************************/
void sp_grow_point( Path* a_long_path, 
       Path* a_short_path )
{
    int   num = a_long_path->m_num;
    int*  src_arr = a_long_path->m_array;

    int max_add_pay = 0;
    int max_pos = 0;
    int max_point = 0;
 int i = 0;

    for( i=1; i<num; i++ )
    {
        int p1 = src_arr[ i - 1 ];
        int p2 = src_arr[ i  ];
        int orig_w = sp_calc_wei( p1, p2 );
        int new_w = orig_w;

        int* neib_arr = SP_GET_NEIB( p2 );
        int neib = 0;
        while( ( neib = *neib_arr++ ) != p2 )
        {
   int w = 0;
   if( SP_IS_POINT_ON_PATH( a_long_path, neib ) )
                continue;

            if( !sp_is_neib( p1, neib ) )
                continue;

   if( SP_IS_POINT_ON_PATH( a_short_path, neib ) )
     continue;

            w = sp_calc_wei( p1, neib ) + 
                    sp_calc_wei( p2, neib );
        
            if( new_w < w )
            {
                new_w = w;

                if( new_w > orig_w )
                {
                    int pay = new_w - orig_w;
                    if( max_add_pay < pay )
                    {
                        max_add_pay = pay;
                        max_pos = i;
                        max_point = neib;
                    }

                }
            }
        }
    }

 sp_add_point( a_long_path, max_pos, max_point );

 sp_set_bk_path( a_short_path );
 SP_TEST_PATH( a_long_path );
}

/***********************************************/
void sp_print_best_path()
{
 if( glb_best_path )
 {
  int i=0; 
  for( i=1; i<glb_best_path->m_num; i++ )
  {
   int point = glb_best_path->m_array[ i ];
   int x = SP_IND_2_X( point );
   int y = SP_IND_2_Y( point );
   printf( "%i %i\n", y, x );
  }
 }
 else
  printf( "\nNo path is found" );
}

/***********************************************/
void  sp_store_short_one( Path* a_path, PathList*  a_list )
{
 int num = a_list->m_num;
 int new_wei = a_path->m_wei;
 int new_num = a_path->m_num;
 int i = 0;

 for( i=num; i>0; i-- )
 {
  int pos = i - 1;
  Path* old_path = a_list->m_arr[ pos ];

  if( ( old_path->m_wei >= new_wei )
   && ( old_path->m_num >= new_num ) )
  {
   pl_del( a_list, pos );
   continue;
  }

  if( ( old_path->m_wei < new_wei )
   && ( old_path->m_num <= new_num ) )
  {
   sp_free_path( a_path );
   return;
  }
 }

 pl_add( a_list, a_path );
}

/***********************************************/
void  sp_find_all_short_one( PathList*  a_list,
        Path*  a_bck_path,
        int    a_max_len,
        int    a_dir )
{
 Path* path = 0;
 glb_short_k1 = 3;
 sp_set_bk_path( a_bck_path );

 if( a_dir )
 {
  sp_start_short_path_search( glb_path_beg, 
    glb_path_end,
    a_max_len + 1 );

  while( path = sp_find_short_path() )
  {
   sp_store_short_one( path, a_list );
  }
 }
 else
 {
  sp_start_short_path_search( glb_path_end, 
    glb_path_beg,
    a_max_len + 1 );

  while( path = sp_find_short_path() )
  {
   path = sp_inverte_path( path );
   sp_store_short_one( path, a_list );
  }
 }
}

/***********************************************/
PathList*  pl_create()
{
 int i=0;
 PathList* list = 
  ( PathList* )malloc( sizeof( PathList ) );
 list->m_arr = ( Path** )malloc( sizeof( Path* )*50);
 list->m_num = 0;
    list->m_size = 50;

 return list;
}

/***********************************************/
void  pl_destroy( PathList* a_path_list )
{
 int i = 0;
 for( i=0; i<a_path_list->m_num; i++ )
 {
  sp_free_path( a_path_list->m_arr[ i ] );
 }
 free( a_path_list->m_arr );
 free( a_path_list );
}

/***********************************************/
void  pl_add( PathList* a_path_list, Path* a_path )
{
 if( a_path_list->m_num >= a_path_list->m_size )
 {
  int new_size = a_path_list->m_size + 50;
  a_path_list->m_arr = 
   ( Path** )realloc( a_path_list->m_arr, 
      sizeof( Path* ) * new_size );
  a_path_list->m_size = new_size;
 }
 a_path_list->m_arr[ a_path_list->m_num++ ] = a_path;
}

/***********************************************/
void  pl_del( PathList* a_path_list, int a_pos )
{
 int to_move = a_path_list->m_num - a_pos - 1;
 sp_free_path( a_path_list->m_arr[ a_pos ] );

 if( to_move )
 {
  memmove( a_path_list->m_arr + a_pos,
    a_path_list->m_arr + a_pos + 1,
    to_move * sizeof( Path* ) );
 }
 a_path_list->m_num--;
}

/***********************************************/
void  sp_add_point( Path* a_path, int a_pos, int a_point )
{
    int to_move = a_path->m_num - a_pos;
    memmove( a_path->m_array + a_pos + 1,
             a_path->m_array + a_pos,
             to_move * sizeof( int ) );

    a_path->m_array[ a_pos ] = a_point;
    a_path->m_num++;

 a_path->m_map[ a_point >> 5 ] |= 
  glb_masks[ a_point & 0x1F ];
}

/***********************************************/
void  sp_append_point( Path* a_path, unsigned int a_point )
{
 a_path->m_array[ a_path->m_num++ ] = a_point;
 a_path->m_map[ a_point >> 5 ] |= 
  glb_masks[ a_point & 0x1F ];
}

/***********************************************/
int  sp_find_ins_point_short( int a_val )
{
 int mid_pos;
 int a_left = 0;
 int a_right = glb_queue_len;

bg: if( a_left + 15 > a_right )
 {
  int i=a_left;
  for( ; i<a_right; i++ )
  {
   if( glb_queue_arr[ i ]->m_val <= a_val )
    return i;
  }

  return a_right;
 }

 mid_pos = ( a_right + a_left ) / 2;
 if( glb_queue_arr[ mid_pos ]->m_val <= a_val )
  a_right = mid_pos;
 else
  a_left = mid_pos;

 goto bg;
}

/***********************************************/
int  sp_find_ins_point( int a_val )
{
 int mid_pos;
 int a_left = 0;
 int a_right = glb_queue_len;

bg: if( a_left + 15 > a_right )
 {
  int i=a_left;
  for( ; i<a_right; i++ )
  {
   if( glb_queue_arr[ i ]->m_val >= a_val )
    return i;
  }

  return a_right;
 }

 mid_pos = ( a_right + a_left ) / 2;
 if( glb_queue_arr[ mid_pos ]->m_val >= a_val )
  a_right = mid_pos;
 else
  a_left = mid_pos;

 goto bg;
}

/***********************************************/
void sp_rem_pathes_on_point( int a_point )
{
 int i=0;
 int offs = a_point >> 5;
 int mask = glb_masks[ ( a_point  ) & 0x1F ];

 for( ; i<glb_queue_len; i++ )
 {
  if( ( glb_queue_arr[ i ]->m_map[ offs ] ) & mask )
  {
    sp_rem_path_from_queue( i-- );
  }
 }
}

/***********************************************/
#define MAXTIME 550
/* 10 minutes worth of seconds */

static time_t Started;
static time_t Current; 
static int     glb_time_over = 0;
void inittime() 
{
 time( &Started );
}

int checktime() 
{ 
 static int counter = 0;
 if( glb_time_over )
  return 0;

 if( counter++ > 100 )
 {
  counter = 0;
  time( &Current );
  if( difftime( Current, Started ) > MAXTIME ) 
  {  
   glb_time_over = 1;
   return 0;
  }
 }

 return 1;
}

/***********************************************/
void main_prepare( int argc, char* argv[] )
{
    char* file = 0;
 int mask = 1;
    int i=0 ;

 inittime();

    if( argc < 2 )
    {
        printf( "\nError in parameters: "
       "no data file name" );
        exit( 0 );
    }

    file = argv[ 1 ];
    if( !sp_read_data_file( file ) )
    {
        printf( "\nError reading data file [%s]", file );
        exit( 0 );
    }

 glb_path_pool = pl_create();
 glb_free_path_num = 0;

 glb_path_beg = SP_XY_2_IND( 0, 0 );
 glb_path_end = SP_XY_2_IND( glb_w - 1, glb_h - 1 );

 glb_path_map_size = ( ( glb_w * glb_h ) / 
       ( 32 * 1 ) ) + 1;
 for( i=0; i<32; i++ )
 {
  glb_masks[ i ] = mask;
  mask = mask << 1;
 }
}

/***********************************************/
void main_xxx()
{
    int i=0 ;
 int num = 0;
 PathList*  short_pathes = 0;

 short_pathes = pl_create();
 sp_find_all_short_one( short_pathes,  
                     0, glb_path_max_len, 0 );

 num = short_pathes->m_num;
#ifdef SP_DEB_OUTPUT
 printf( "init short num=%i\n", num );
#endif

 for( i=0; i<num; i++ )
 {
  main_on_short( short_pathes->m_arr[ i ] );
 }

 /* second round */
 sp_find_all_short_one( short_pathes,  
                     0, glb_path_max_len, 1 );
 num = short_pathes->m_num;
#ifdef SP_DEB_OUTPUT
 printf( "init short num=%i\n", num );
#endif

 for( ; i<num; i++ )
 {
  main_on_short( short_pathes->m_arr[ i ] );
 }

 pl_destroy( short_pathes );
}

/***********************************************/
int main( int argc, char* argv[] )
{
 main_prepare( argc, argv );

 main_xxx();

#ifndef SP_DEB_OUTPUT
 sp_print_best_path();
#endif

    sp_free_resources();

#ifdef SP_DEB_WAIT
 printf( "\n?" );
 getchar(); 
#endif

    return 1;
}

/***********************************************/
void  main_on_short( Path* a_short_path )
{
 int wei = a_short_path->m_wei;
 int len = a_short_path->m_num - 1;
 int long_len = 0;
 int snum = 0;
 int n = 0;
 PathList*  new_short_pathes = 0;
 Path* long_path = 0;

 sp_set_bk_path( 0 );
 glb_long_k1 = 2;

 long_path = sp_find_best_long_path( 
        glb_path_max_len - len,
        a_short_path );
 if( long_path )
 {
  while( glb_path_max_len > 
   ( a_short_path->m_num + long_path->m_num  - 2 ) )
  {
   sp_grow_point( long_path, a_short_path );
  }

  sp_on_ready_path( a_short_path, long_path );
  sp_free_path( long_path );
 }

 /* reverse search : start from long path */
 long_path = sp_find_best_long_path( 
     glb_path_max_len - len, 0 );

 if( !long_path )
  return;

 long_len = long_path->m_num - 1;

 new_short_pathes = pl_create();

 /* search all compliment short pathes */
 sp_find_all_short_one( new_short_pathes, 
         long_path, len, 0 );

 snum = new_short_pathes->m_num;

 for( n = 0; n<snum; n++ )
 {
  Path* new_long_path = sp_clone_path( long_path );
  Path* new_short_path = 
   new_short_pathes->m_arr[ n ];

  while( glb_path_max_len > 
   ( new_short_path->m_num + 
    new_long_path->m_num  - 2 ) )
  {
   sp_grow_point( new_long_path, 
    new_short_path );
  }
     
  if( glb_path_max_len 
   < ( new_short_path->m_num 
    + new_long_path->m_num  - 2 ) )
  {
   continue;
   sp_free_path( new_long_path );
  }

  sp_on_ready_path( new_short_path, 
             new_long_path );

  sp_free_path( new_long_path );
 }

 /* search all compliment short pathes     
    in reverse direction */

 sp_find_all_short_one( new_short_pathes, 
         long_path, len, 1 );

 snum = new_short_pathes->m_num;

 for( ; n<snum; n++ )
 {
  Path* new_long_path = sp_clone_path( long_path );
  Path* new_short_path = 
   new_short_pathes->m_arr[ n ];

  while( glb_path_max_len > 
   ( new_short_path->m_num + 
    new_long_path->m_num  - 2 ) )
  {
   sp_grow_point( new_long_path, 
    new_short_path );
  }
     
  if( glb_path_max_len 
   < ( new_short_path->m_num 
    + new_long_path->m_num  - 2 ) )
  {
   continue;
   sp_free_path( new_long_path );
  }

  sp_on_ready_path( new_short_path, 
     new_long_path );
  sp_free_path( new_long_path );
 }

 pl_destroy( new_short_pathes );
}

/***********************************************/
void sp_push_long_path_in_queue( Path* a_path )
{
 int new_val = a_path->m_val;
 int new_head = a_path->m_array[ a_path->m_num - 1 ];

 if( glb_best_vals[ new_head ] )
  sp_rem_pathes_on_point( new_head ); 

 glb_best_vals[ new_head ] = new_val;
 sp_insert_path_in_queue( sp_find_ins_point( new_val ),
        a_path );


 if( glb_queue_len > 150 )
 {
  while( glb_queue_len > 140 )
   sp_rem_path_from_queue( 0 );
 }
}

/***********************************************/
void sp_push_short_path_in_queue( Path* a_path )
{
	int new_val = a_path->m_val;
	int new_head = a_path->m_array[ a_path->m_num - 1 ];
	int i=0;

	sp_insert_path_in_queue( 
		sp_find_ins_point_short( new_val ),
							 a_path );

	glb_best_vals[ new_head ] = new_val;
}

/***********************************************/