/* Note from the POTM-MASTER:  while the limit on entries is
	25,000 characters, I always give contestants the
	opportunity to add comments, expand variable names,
	"un-cstrip" their code, and do whatever they wish to
	make it more readable without changing the functionality
	of the code before it is posted on the web.		*/

    /*  ---------------<< COMMENTED VERSION >>----------------- */
    /*                 *** Scenic Tour POTM ***                 */
    /*  POTM ENTRY:  Walking_with_my_dog                        */
    /*  My Name:     Guillermo Sais                             */
    /*  My email:    gsais@iname.com                            */
    /*  Directions:  compile in C++                             */
    /*  ------------------------------------------------------- */
    /*            PERMISSION IS GRANTED TO EVERYONE             */
    /*          TO USE THIS SOURCE WITHOUT LIMITATIONS          */
    /* -------------------------------------------------------- */
    /*  Note to the reader: I'll be very happy if anyone founds */
    /*  this code interesting. I'll gladly answer any questions */
    /*  if I had the time (just e-mail me at the address above) */
    /* -------------------------------------------------------- */

#include                <mem.h>
#include                <stdio.h>
#include                <stdlib.h>
#include                <string.h>
#include                <time.h>
#include                <sys/times.h>

// some useful definitions:
#define                 False                   0
#define                 True                    1
#define                 nMaxInt                 2147483647
typedef                 int                     boolean;

// fAbs: returns the absolute value or a integer (identical to abs)
inline int              fAbs                    (int x)
  {
  return (x<0)? -x:x;
  }

// fGetTime: gets the number of seconds elapsed since a particular time (it's
//           not really important to know that 'particular' time, as long as
//           it doesn't change between function calls).
inline int              fGetTime                ()
  {
  static struct tms     Time;

  times(&Time);
  return (Time.tms_stime+Time.tms_utime)/nTimeConstant;
  }

                         /*** Constant definitions ***/

enum
  {
  nMinSize              = 10,                   // minimum size/grid
  nMaxSize              = 255,                  // maximum size/grid
  nMinLimit             = 4,                    // minimum limit (relative to size)
  nMaxLimit             = 20,                   // maximum limit (relative to size)
  nMaxEdges             = 8,                    // maximum edges/node
  nMinValue             = 0,                    // minimum height value
  nMaxValue             = 255,                  // maximum height value
  nMaxSegments          = 16,                   // maximum segments
  nMaxTime              = 600-30,               // maximum time (seconds)
  nTimerDivisor         = 10000,                // check time every 'n' operations
  nTimeConstant         = 100,                  // system-dependent constant
  nTreshold             = nMaxValue+1,          // Treshold value (height)
  nMaxWidth             = nMaxSize,             // maximum width/grid
  nMaxHeight            = nMaxSize,             // maximum height/grid
  nMaxNodes             = nMaxWidth*nMaxHeight, // maximum nodes/grid
  nMaxPoints            = nMaxSize*(nMaxLimit*2), // maximum points/path
  };

// nDeltaX=relative horizontal offset to connected nodes
const int               nDeltaX[nMaxEdges]={+1,+1,+0,-1,-1,-1,+0,+1};

// nDeltaY=relative vertical offset to connected nodes
const int               nDeltaY[nMaxEdges]={+0,+1,+1,+1,+0,-1,-1,-1};


                         /*** Forward declarations ***/

// declarations for all classes:
class                   tTimer;
class                   tEdge;
class                   tEdgeList;
class                   tNode;
class                   tNodeList;
class                   tPoint;
class                   tPath;
class                   tGraph;
class                   tProblem;
class                   tSolution;
class                   tSegment;
class                   tScenicTour;

// declarations for pointers to all classes:
typedef                 tTimer*                 tTimerPtr;
typedef                 tEdge*                  tEdgePtr;
typedef                 tEdgeList*              tEdgeListPtr;
typedef                 tNode*                  tNodePtr;
typedef                 tNodeList*              tNodeListPtr;
typedef                 tPoint*                 tPointPtr;
typedef                 tPath*                  tPathPtr;
typedef                 tGraph*                 tGraphPtr;
typedef                 tProblem*               tProblemPtr;
typedef                 tSolution*              tSolutionPtr;
typedef                 tSegment*               tSegmentPtr;
typedef                 tScenicTour*            tScenicTourPtr;

// declarations for functions:
static void             fExit                   ();


                          /*** Class declarations ***/

/* ------------------------------------------------------------------------- */
// tTimer: checks elapsed time since program start
class                   tTimer
  {
  public:
    int                 pStartTime;             // initial time (seconds)

  public:
    // fStart: sets initial time
    inline void         fStart                  ()
      {
      pStartTime=fGetTime();
      }

    // fCheck: checks if time is over. If so, calls fExit()
    inline void         fCheck                  ()
      {
      if(fGetTime()-pStartTime>=nMaxTime) fExit();
      }
  };


/* ------------------------------------------------------------------------- */
// tEdge: describes a edge (connection) between two nodes (grid points).
//        A tEdge is always inside a tEdgeList!
class                   tEdge
  {
  public:
    int                 pWeight;                // weight of edge
                                                // weight=distance (for shortest path)
                                                // weight=treshold-distance (for longest path)
    int                 pDistance;              // distance between nodes
    tNodePtr            pNode;                  // target node (source node is implicit)
  };


/* ------------------------------------------------------------------------- */
// tEdgeList: describes a list of edges, between *one* node and connected nodes
class                   tEdgeList
  {
  public:
    int                 pCount;                 // number of edges in list
    tEdge               pItems[nMaxEdges];      // the edges themselves

  public:
    // fClear: empties the list (sets count to zero)
    inline void         fClear                  ()
      {
      pCount=0;
      }

    // fAddItem: adds a edge to the list
    //   aWeight:       weight of the edge, equal to distance for shortest path,
    //                   equal to treshold minus distance for longest path
    //   aDistance:     distance between source node and target node
    //   aNode:         target node (source node is implicit)
    inline void         fAddItem                (int aWeight,
                                                int aDistance,
                                                tNodePtr aNode)
      {
      pItems[pCount].pWeight=aWeight;
      pItems[pCount].pDistance=aDistance;
      pItems[pCount].pNode=aNode;
      pCount++;
      }
  };


/* ------------------------------------------------------------------------- */
// tNode: describes a node (grid point). A tNode is *always* inside a tNodeList!
class                   tNode
  {
  public:
    int                 pPosX;                  // horizontal position
    int                 pPosY;                  // vertical position
    int                 pIndex;                 // node index (within the tNodeList)
    int                 pMinWeight;             // minimum weight (from a particular node)
    int                 pMinDistance;           // minimum distance (from the same particular node)
    int                 pMinMoves;              // minimum moves (from the same particular node)
    int                 pMinEdge;               // previous 'minimum' node (from the same particular node)
    tEdgeList           pEdges;                 // list of edges from this node to
                                                // surrounding nodes
  };


/* ------------------------------------------------------------------------- */
// tNodeList: describes a list of nodes; tNodeList is "almost" a graph, but a
//            graph contains more information (see tGraph below)
class                   tNodeList
  {
  public:
    int                 pCount;                 // number of nodes on the list
    tNode               pItems[nMaxNodes];      // the nodes themselves

  public:
    // fClear: empties the list (sets count to zero)
    inline void         fClear                  ()
      {
      pCount=0;
      }

    // fAddItem: adds a node to the list
    //   aPosX:         horizontal position of the node
    //   aPosY:         vertical position of the node
    //   returns:       pointer to the new node
    inline tNodePtr     fAddItem                (int aPosX,
                                                int aPosY)
      {
      pItems[pCount].pPosX=aPosX;
      pItems[pCount].pPosY=aPosY;
      pItems[pCount].pIndex=pCount;
      pItems[pCount].pMinWeight=nMaxInt;
      pItems[pCount].pMinDistance=nMaxInt;
      pItems[pCount].pMinMoves=nMaxInt;
      pItems[pCount].pMinEdge=-1;
      pItems[pCount].pEdges.fClear();
      return &(pItems[pCount++]);
      }
  };


/* ------------------------------------------------------------------------- */
// tPoint: describes a point (a coordinate pair, containing the horizontal
//         position and the vertical position of the point). A tPoint is
//         *always* inside a tPath!
class                   tPoint
  {
  public:
    int                 pPosX;                  // the horizontal position of the point
    int                 pPosY;                  // the vertical position of the point
  };

/* ------------------------------------------------------------------------- */
// tPath: describes a path between two nodes in a graph, using a list of
//        points. The source point of the path *and* the target point of the
//        path are included in the list.
class                   tPath
  {
  public:
    int                 pCount;                 // number of points in the path
    tPoint              pItems[nMaxPoints];     // the points themselves

  public:
    // fClear: empties the path (sets count to zero)
    inline void         fClear                  ()
      {
      pCount=0;
      }

    // fAddItem: adds a point to the path
    //   aPosX:         horizontal position of the point
    //   aPosY:         vertical position of the point
    inline void         fAddItem                (int aPosX,
                                                int aPosY)
      {
      pItems[pCount].pPosX=aPosX;
      pItems[pCount].pPosY=aPosY;
      pCount++;
      }

    // fSetItem: changes a point in the path
    //   aIndex:        index of the point to change
    //   aPosX:         new horizontal position of the point
    //   aPosY:         new vertical position of the point
    inline void         fSetItem                (int aIndex,
                                                int aPosX,
                                                int aPosY)
      {
      pItems[aIndex].pPosX=aPosX;
      pItems[aIndex].pPosY=aPosY;
      }

    // fInsertItem: inserts a point in the path
    //   aIndex:        index at which the point is inserted
    //   aPosX:         horizontal position of the point to insert
    //   aPosY:         vertical position of the point to insert
    inline void         fInsertItem             (int aIndex,
                                                int aPosX,
                                                int aPosY)
      {
      memmove(&pItems[aIndex+1],&pItems[aIndex],(pCount-aIndex)*sizeof(tPoint));
      pItems[aIndex].pPosX=aPosX;
      pItems[aIndex].pPosY=aPosY;
      pCount++;
      }

    // fAddPath: adds another path to this path
    //   aPath:         the path to be added
    inline void         fAddPath                (const tPath& aPath)
      {
      if(aPath.pCount>0)
        {
        memcpy(&pItems[pCount],aPath.pItems,aPath.pCount*sizeof(tPoint));
        pCount+=aPath.pCount;
        }
      }

    // fAssign: copies another path into this path
    //   aPath:         the path to be copied
    inline void         fAssign                 (const tPath& aPath)
      {
      if((pCount=aPath.pCount)>0)
        memcpy(pItems,aPath.pItems,pCount*sizeof(tPoint));
      }
  };


/* ------------------------------------------------------------------------- */
// tGraph: describes a 'geographic' graph. Contains a list of nodes, a list
//         of edges between nodes (described in each node), and a 'map' between
//         grid points and nodes
class                   tGraph
  {
  public:
    int                 pWidth;                 // width of the map
    int                 pHeight;                // height of the map
    tNodeList           pNodes;                 // list of nodes
    tNodePtr            pNodesMap[nMaxWidth][nMaxHeight];
                                                // 'map' between grid points
                                                // and nodes

  public:
    // fAddEdge: creates a edge between two nodes
    //   aSrcX,aSrcY:   position of the source node
    //   aTgtY,aTgtY:   position of the target node
    //   aWeight:       weight of the edge
    //   aDistance:     distance between the source node and the target node
    inline void         fAddEdge                (int aSrcX,
                                                int aSrcY,
                                                int aTgtX,
                                                int aTgtY,
                                                int aWeight,
                                                int aDistance)
      {
      pNodesMap[aSrcX][aSrcY]->pEdges.fAddItem(aWeight,aDistance,pNodesMap[aTgtX][aTgtY]);
      }

    // fFindEdge: determines the position of one of the eight connected nodes
    //            to another node (only if it's within the grid limits)
    //   aDelta:        index to the edge direction (from 0 to 7); the first
    //                  direction is right, and it advances in counter-clockwise
    //                  direction (this parameter is actually a index to the
    //                  tables nDeltaX and nDeltaY)
    //   aSrcX,aSrcY:   position of the source node
    //   returns:       false if the target node exists, true otherwise
    //   aTgtX,aTgtY:   position of the target node (output)
    inline boolean      fFindEdge               (int aDelta,
                                                int aSrcX,
                                                int aSrcY,
                                                int& aTgtX,
                                                int& aTgtY)
      {
      aTgtX=aSrcX+nDeltaX[aDelta];
      if((aTgtX<0)||(aTgtX>=pWidth)) return False;
      aTgtY=aSrcY+nDeltaY[aDelta];
      if((aTgtY<0)||(aTgtY>=pHeight)) return False;
      return pNodesMap[aTgtX][aTgtY]!=NULL;
      }

    // fBuildNodes: creates *all* the nodes within a grid
    //   aWidth:        width of the grid
    //   aHeight:       height of the grid
    inline void         fBuildNodes             (int aWidth,
                                                int aHeight)
      {
      int               x,y;

      pWidth=aWidth;
      pHeight=aHeight;
      pNodes.fClear();
      for(x=0;x<aWidth;x++)
        for(y=0;y<aHeight;y++)
          pNodesMap[x][y]=pNodes.fAddItem(x,y);
      }

    // fRemovePath: removes the nodes contained in a path. This function must
    //              be called *after* calling fBuildNodes!
    //   aPath:         path to be removed from the graph
    //   aRemoveFirst:  flag that indicates if the first point in the path is to be removed
    //   aRemoveLast:   flag that indicates if the last point in the path is to be removed
    inline void         fRemovePath             (const tPath& aPath,
                                                boolean aRemoveFirst,
                                                boolean aRemoveLast)
      {
      int               i,n;

      n=aPath.pCount-((aRemoveLast)? 0:1);
      for(i=((aRemoveFirst)? 0:1);i<n;i++)
        pNodesMap[aPath.pItems[i].pPosX][aPath.pItems[i].pPosY]=NULL;
      }

    // fGetMinPath: gets the minimum-weight path between a point and the source
    //              point passed to fFindMinPaths. This function must be called
    //              *after* calling fFindMinPaths (see below)!
    //   aTargetX:      horizontal position of target node
    //   aTargetY:      vertical position of target node
    //   returns:
    //   aPath:         minimum-weight path between target and source
    inline void         fGetMinPath             (int aTargetX,
                                                int aTargetY,
                                                tPath& aPath)
      {
      int               i,n;
      tNodePtr          node;

      node=pNodesMap[aTargetX][aTargetY];
      aPath.pCount=(n=node->pMinMoves)+1;
      for(;;)
        {
        aPath.fSetItem(n--,node->pPosX,node->pPosY);
        if((i=node->pMinEdge)<0) break;
        node=node->pEdges.pItems[i].pNode;
        }
      }

    // fGetMinPathInv: does the same as fGetMinPath, but the resulting path
    //                 contains the points inverted (from the source to the
    //                 target).
    inline void         fGetMinPathInv          (int aTargetX,
                                                int aTargetY,
                                                tPath& aPath)
      {
      int               i;
      tNodePtr          node;

      aPath.fClear();
      node=pNodesMap[aTargetX][aTargetY];
      for(;;)
        {
        aPath.fAddItem(node->pPosX,node->pPosY);
        if((i=node->pMinEdge)<0) break;
        node=node->pEdges.pItems[i].pNode;
        }
      }

    // fBuildEdges: builds all the edges between all the nodes in the grid,
    //              except those nodes that have been removed from the graph
    //              (using fRemovePath).
    //   aProblem:      reference to the problem that contains the height for
    //                  each point in the grid
    void                fBuildEdges             (const tProblem& aProblem);

    // fBuildEdgesInv: does the same as fBuildEdges, but instead of setting
    //                 weight=distance, it sets weight=treshold-distance
    void                fBuildEdgesInv          (const tProblem& aProblem,
                                                int aTreshold);

    // fFindMinPaths: finds the minimum-weight distance between a source point
    //                and *all* other nodes in the graph.
    //   aSourceX:      horizontal position of source node
    //   aSourceY:      vertical position of source node
    void                fFindMinPaths           (int aSourceX,
                                                int aSourceY);

    // fExpandPath: expands ('maximizes') a minimum-weight path, inserting
    //              the nodes that maximizes the distance (used for the
    //              intermediate longest paths)
    // aPath:           path to be expanded
    // aAvailable:      number of nodes available
    // returns:
    // aPath:           expanded path
    void                fExpandPath             (tPath& aPath,
                                                int aAvailable);
  };


/* ------------------------------------------------------------------------- */
// tProblem: describes the input data of the problem (limit, size, heights...)
class                   tProblem
  {
  public:
    int                 pLimit;                 // maximum moves in the path
    int                 pSize;                  // size of the grid
    int                 pWidth;                 // width of the grid (equal to size)
    int                 pHeight;                // height of the grid (equal to size)
    int                 pSourceX;               // horizontal position of the origin (0)
    int                 pSourceY;               // vertical position of the origin (0)
    int                 pTargetX;               // horizontal position of the destination (size-1)
    int                 pTargetY;               // vertical position of the destination (size-1)
    int                 pHeightGrid[nMaxWidth][nMaxHeight];
                                                // heights for each point in the grid

  public:
    // fGetPathDistance: gets the total distance travelled in a path
    //   aPath:         path to be travelled
    //   returns:       total distance
    inline int          fGetPathDistance        (const tPath& aPath)
      {
      int               i,n,r,z,z0;

      for(i=r=z=0,n=aPath.pCount;i<n;i++)
        {
        z0=z;
        z=pHeightGrid[aPath.pItems[i].pPosX][aPath.pItems[i].pPosY];
        if(i>0) r+=fAbs(z-z0);
        }
      return r;
      }

    // fRead: reads the input data from a text file
    //   aFileName:     name of input file
    //   returns:       true if succesful, false otherwise
    boolean             fRead                   (const char* aFileName);

    // fGetPathScore: gets the short score, long score, the score, and the
    //                number of moves in a path (go and back)
    //   aPath:         go and back path
    //   returns:       true if the path is legal, false otherwise
    //   aMoves:        number of moves in the path
    //   aShortScore:   short score of the path (distance travelled in the going)
    //   aLongScore:    long score of the path (distance travelled in the back)
    //   aScore:        score of the path (long_score/short_score)
    boolean             fGetPathScore           (const tPath& aPath,
                                                int& aMoves,
                                                int& aShortScore,
                                                int& aLongScore,
                                                double& aScore);
  };


/* ------------------------------------------------------------------------- */
// tSolution: describes one solution to the problem
class                   tSolution
  {
  public:
    int                 pMoves;                 // number of moves in the solution
    int                 pShortScore;            // short score of the solution
    int                 pLongScore;             // long score of the solution
    double              pScore;                 // score of the solution
    tPath               pPath;                  // solution path (going and back)

  public:
    // fClear: empties the solution (actually finds a simple worst-is-nothing
    //         solution)
    inline void         fClear                  (tProblem& aProblem)
      {
      int               x,y,cx,cy;

      cx=aProblem.pWidth-1;
      cy=aProblem.pHeight-1;
      pPath.fClear();
      for(x=0;x<=cx;x++) pPath.fAddItem(x,0);
      for(y=1;y<cy;y++) pPath.fAddItem(cx,y);
      for(x=cx;x>=1;x--) pPath.fAddItem(x,cy);
      for(y=cy;y>=0;y--) pPath.fAddItem(0,y);
      aProblem.fGetPathScore(pPath,pMoves,pShortScore,pLongScore,pScore);
      }

    // fCopy: copies the solution from two paths (one for the going and the
    //        other for the back), and calculates the score.
    //   aProblem:      reference to the input data (needed to calculate the
    //                  score)
    //   aGoingPath:    path from the origin to the destination
    //   aBackPath:     path from the destination to the origin
    inline void         fCopy                   (tProblem& aProblem,
                                                const tPath& aGoingPath,
                                                const tPath& aBackPath)
      {
      pPath.fClear();
      pPath.fAddPath(aGoingPath);
      pPath.pCount--;
      pPath.fAddPath(aBackPath);
      aProblem.fGetPathScore(pPath,pMoves,pShortScore,pLongScore,pScore);
      }

    // fPrint: prints the solution, one point by line, with the format "y x\n"
    inline void         fPrint                  ()
      {
      int               i;
      for(i=1;i<pPath.pCount;i++)
        printf("%d %d\n",pPath.pItems[i].pPosY,pPath.pItems[i].pPosX);
      }
  };


/* ------------------------------------------------------------------------- */
// tSegment: defines a 'segment' of a longest-path
class                   tSegment
  {
  public:
    int                 pScore;                 // score of the segment
    int                 pMoves;                 // number of moves in the segment
    tPoint              pPoint;                 // source point of the segment
                                                // (the target point is implicit,
                                                // because is the source point of
                                                // the next segment)
    tPath               pPath;                  // the segment itself (a subpath)
  };


/* ------------------------------- MAIN CLASS ------------------------------ */
// tScenicTour: defines a "Scenic Tour" problem; the input data, the best
//              solution, and the algorithm for solving it.
class                   tScenicTour
  {
  public:
    int                 pWidth,pHeight,pLimit;
    int                 pSourceX,pSourceY,pTargetX,pTargetY;
    int                 pAvailable,pSegmentsCount;
    tProblem            pProblem;
    tSolution           pSolution,pBestSolution;
    tGraph              pGoingGraph,pBackGraph,pGraph1,pGraph2;
    tPath               pGoingPath,pBackPath,pPath1,pPath2,pBestPath1,pBestPath2;
    tSegment            pSegments[nMaxSegments+1];

  public:
    // fRead: reads the input data from a text file, clears the best solution,
    //        and inits the input properties (size, width, height, limit, ...)
    //   aFileName:     name of input file
    inline void         fRead                   (const char* aFileName)
      {
      pProblem.fRead(aFileName);
      pBestSolution.fClear(pProblem);
      pWidth=pProblem.pWidth;
      pHeight=pProblem.pHeight;
      pLimit=pProblem.pLimit;
      pSourceX=pProblem.pSourceX;
      pSourceY=pProblem.pSourceY;
      pTargetX=pProblem.pTargetX;
      pTargetY=pProblem.pTargetY;
      }

    // fPrint: prints the best solution
    inline void         fPrint                  ()
      {
      pBestSolution.fPrint();
      }

    // fSolve: finds the best solution (going and back path)
    void                fSolve                  ();

    // fSolveGoing: finds the best path for the going path
    void                fSolveGoing             ();

    // fSolveBack: finds the best path for the back path
    //   aDivisor:      this parameter specifies how long it should try to
    //                  find solutions (the smaller values of aDivisor are
    //                  faster than the larger values, but these usually find
    //                  better solutions)
    //   aFastLevel:    this parameter also helps finding solutions fast; it
    //                  specifies when to ignore the aDivisor parameter (the
    //                  larger values of aFastLevel are faster than the smaller
    //                  values, but these usually find better solutions)
    void                fSolveBack              (int aDivisor,
                                                int aFastLevel);

    // fOptimize: optimizes a path by sub-dividing it in smaller segments
    //            (used only for the longest path)
    //   aDivisor:      same as aDivisor in fSolveBack
    //   aFastLevel:    same as aFastLevel in fSolveBack
    void                fOptimize               (int aDivisor,
                                                int aFastLevel);
  };


                         /*** Variable definitions ***/

static tTimer           Timer;                  // global timer
static tScenicTourPtr   ScenicTour;             // the problem itself


                         /*** Function definitions ***/

// fExit: prints the solution and exits the program
static void             fExit                   ()
  {

  ScenicTour->fPrint();
  exit(0);
  }

// fBuildEdges: builds all the edges between all the nodes in the grid,
//              except those nodes that have been removed from the graph
//              (using fRemovePath).
//   aProblem:  reference to the problem that contains the height for
//              each point in the grid
void                    tGraph::fBuildEdges     (const tProblem& aProblem)
  {
  int                   i,x,y,z,dx,dy,dz;
  int                   Distance,Weight;

  for(x=0;x<pWidth;x++)
    for(y=0;y<pHeight;y++)
      {
      if(pNodesMap[x][y]==NULL) continue;
      z=aProblem.pHeightGrid[x][y];
      for(i=0;i<nMaxEdges;i++)
        {
        if(!fFindEdge(i,x,y,dx,dy)) continue;
        dz=aProblem.pHeightGrid[dx][dy];
        Weight=Distance=fAbs(z-dz);
        fAddEdge(x,y,dx,dy,Weight,Distance);
        }
      }
  }

// fBuildEdgesInv: does the same as fBuildEdges, but instead of setting
//                 weight=distance, it sets weight=treshold-distance
void                    tGraph::fBuildEdgesInv  (const tProblem& aProblem,
                                                int aTreshold)
  {
  int                   i,x,y,z,dx,dy,dz;
  int                   Distance,Weight;

  for(x=0;x<pWidth;x++)
    for(y=0;y<pHeight;y++)
      {
      if(pNodesMap[x][y]==NULL) continue;
      z=aProblem.pHeightGrid[x][y];
      for(i=0;i<nMaxEdges;i++)
        {
        if(!fFindEdge(i,x,y,dx,dy)) continue;
        dz=aProblem.pHeightGrid[dx][dy];
        Distance=fAbs(z-dz);
        Weight=aTreshold-Distance;
        fAddEdge(x,y,dx,dy,Weight,Distance);
        }
      }
  }

// fFindMinPaths: finds the minimum-weight distance between a source point
//                and *all* other nodes in the graph.
//   aSourceX:          horizontal position of source node
//   aSourceY:          vertical position of source node
void                    tGraph::fFindMinPaths   (int aSourceX,
                                                int aSourceY)
  {
  int                   d,e,i,j,k,n,nodes,min,dist,moves,iter;
  tNodePtr              org,src,tgt;
  tEdgePtr              edge;
  static boolean        changed[nMaxNodes];
  static int            begin,end;
  static tNodePtr       list[nMaxNodes+1];

  org=pNodesMap[aSourceX][aSourceY];
  org->pMinWeight=org->pMinDistance=org->pMinMoves=0;
  org->pMinEdge=-1;
  begin=end=0;
  nodes=pNodes.pCount;
  for(i=0;i<nodes;i++) changed[i]=False;
  for(i=0,n=org->pEdges.pCount;i<n;i++)
    {
    tgt=org->pEdges.pItems[i].pNode;
    if(changed[tgt->pIndex]) continue;
    changed[tgt->pIndex]=True;
    list[end]=tgt;
    if(++end>nodes) end=0;
    }
  for(iter=0;begin!=end;iter++)
    {
    if((iter%nTimerDivisor)==0) Timer.fCheck();
    src=list[begin];
    min=src->pMinWeight;
    moves=src->pMinMoves;
    for(i=0,j=-1,n=src->pEdges.pCount;i<n;i++)
      {
      edge=&(src->pEdges.pItems[i]);
      tgt=edge->pNode;
      if((d=tgt->pMinWeight)==nMaxInt) continue;
      d+=edge->pWeight;
      if(d>min) continue;
      e=tgt->pMinMoves+1;
      if((d==min)&&(e>=moves)) continue;
      j=i,min=d,moves=e;
      dist=tgt->pMinDistance+edge->pDistance;
      }
    if(j>=0)
      {
      src->pMinWeight=min;
      src->pMinDistance=dist;
      src->pMinMoves=moves;
      src->pMinEdge=j;
      for(i=0,n=src->pEdges.pCount;i<n;i++)
        {
        if(i==j) continue;
        tgt=src->pEdges.pItems[i].pNode;
        if(changed[k=tgt->pIndex]) continue;
        changed[k]=True;
        list[end]=tgt;
        if(++end>nodes) end=0;
        }
      }
    changed[src->pIndex]=False;
    if(++begin>nodes) begin=0;
    }
  }

// fExpandPath: expands ('maximizes') a minimum-weight path, inserting
//              the nodes that maximizes the distance (used for the
//              intermediate longest paths)
// aPath:               path to be expanded
// aAvailable:          number of nodes available
// returns:
// aPath:               expanded path
void                    tGraph::fExpandPath     (tPath& aPath,
                                                int aAvailable)
  {
  int                   d,i,j,k;
  int                   MaxDist,MaxIdx,MaxX,MaxY;
  tNodePtr              src,tgt,ins;
  static boolean        used[nMaxNodes];

  if(aAvailable<=0) return;
  for(i=0;i<pNodes.pCount;i++)
    used[i]=False;
  for(i=0;i<aPath.pCount;i++)
    used[pNodesMap[aPath.pItems[i].pPosX][aPath.pItems[i].pPosY]->pIndex]=True;
  while(aAvailable>0)
    {
    MaxDist=0,MaxIdx=MaxX=MaxY=-1;
    for(i=1;i<aPath.pCount;i++)
      {
      src=pNodesMap[aPath.pItems[i-1].pPosX][aPath.pItems[i-1].pPosY];
      tgt=pNodesMap[aPath.pItems[i].pPosX][aPath.pItems[i].pPosY];
      for(j=0;j<src->pEdges.pCount;j++)
        {
        ins=src->pEdges.pItems[j].pNode;
        if(used[ins->pIndex]) continue;
        for(k=0;k<tgt->pEdges.pCount;k++)
          {
          if(ins!=tgt->pEdges.pItems[k].pNode) continue;
          d=src->pEdges.pItems[j].pDistance+tgt->pEdges.pItems[k].pDistance;
          if(d>MaxDist) MaxDist=d,MaxIdx=i,MaxX=ins->pPosX,MaxY=ins->pPosY;
          break;
          }
        }
      }
    if(MaxIdx<0) break;
    aPath.fInsertItem(MaxIdx,MaxX,MaxY);
    used[pNodesMap[MaxX][MaxY]->pIndex]=True;
    aAvailable--;
    }
  }

// fRead: reads the input data from a text file
//   aFileName:         name of input file
//   returns:           true if succesful, false otherwise
boolean                 tProblem::fRead         (const char* aFileName)
  {
  int                   x,y,z;
  char                  s[256],*a,*b;
  FILE                  *f;

  f=fopen(aFileName,"rt");
  if(f==NULL) return False;
  fgets(s,sizeof s,f);
  fgets(s,sizeof s,f);
  sscanf(s,"#%d",&pLimit);
  fgets(s,sizeof s,f);
  sscanf(s,"%d %d",&pWidth,&pHeight);
  pSize=pWidth;
  fgets(s,sizeof s,f);
  for(x=y=0;!feof(f);)
    {
    if(fgets(s,sizeof s,f)==NULL) break;
    for(a=s;*a;a++)
      {
      z=(int) strtol(b=a,&a,10);
      if(a==b) continue;
      pHeightGrid[x][y]=z;
      if(++x>=pWidth) x=0,y++;
      }
    }
  fclose(f);
  pSourceX=pSourceY=0;
  pTargetX=pWidth-1;
  pTargetY=pHeight-1;
  return True;
  }

// fGetPathScore: gets the short score, long score, the score, and the
//                number of moves in a path (go and back)
//   aPath:             going and back path
//   returns:           true if the path is legal, false otherwise
//   aMoves:            number of moves in the path
//   aShortScore:       short score of the path (distance travelled in the going)
//   aLongScore:        long score of the path (distance travelled in the back)
//   aScore:            score of the path (long_score/short_score)
boolean                 tProblem::fGetPathScore (const tPath& aPath,
                                                int& aMoves,
                                                int& aShortScore,
                                                int& aLongScore,
                                                double& aScore)
  {
  int                   i,n,x,y,z,x0,y0,z0,Moves,ShortScore,LongScore;
  boolean               v;
  static boolean        used[nMaxWidth][nMaxHeight];

  aMoves=aShortScore=aLongScore=0;
  aScore=0;
  for(x=0;x<pWidth;x++)
    for(y=0;y<pHeight;y++)
      used[x][y]=False;
  Moves=ShortScore=LongScore=0;
  x=y=z=-1;
  for(i=0,n=aPath.pCount,v=False;i<n;i++)
    {
    x0=x; y0=y; z0=z;
    x=aPath.pItems[i].pPosX;
    if((x<0)||(x>=pWidth)) return False;
    y=aPath.pItems[i].pPosY;
    if((used[x][y])||(y<0)||(y>=pHeight)) return False;
    if((i==0)||(i==n-1))
      if((x!=pSourceX)||(y!=pSourceY)) return False;
    z=pHeightGrid[x][y];
    if(i==0) continue;
    if((fAbs(x-x0)>1)||(fAbs(y-y0)>1)) return False;
    (v? LongScore:ShortScore)+=fAbs(z-z0);
    if((x==pTargetX)&&(y==pTargetY))
      {
      if(v) return False;
      v=True;
      }
    used[x][y]=True;
    Moves++;
    }
  if((!v)||(Moves>pLimit)||(ShortScore==0)) return False;
  aMoves=Moves;
  aLongScore=LongScore;
  aShortScore=ShortScore;
  aScore=((double) LongScore)/ShortScore;
  return True;
  }

// fSolve: finds the best solution (going and back path)
void                    tScenicTour::fSolve     ()
  {
  int                   Divisor;

  fSolveGoing();
  fSolveBack(3,pAvailable);
  fSolveBack(3,pAvailable/2);
  for(Divisor=3;Divisor<=pAvailable*2;Divisor*=2)
    fSolveBack(Divisor,pAvailable/Divisor);
  }

// fSolveGoing: finds the best path for the going path
void                    tScenicTour::fSolveGoing()
  {

  pGoingGraph.fBuildNodes(pWidth,pHeight);
  pGoingGraph.fBuildEdges(pProblem);
  pGoingGraph.fFindMinPaths(pSourceX,pSourceY);
  pGoingGraph.fGetMinPath(pTargetX,pTargetY,pGoingPath);
  pBackGraph.fBuildNodes(pWidth,pHeight);
  pBackGraph.fRemovePath(pGoingPath,False,False);
  pBackGraph.fBuildEdgesInv(pProblem,nTreshold);
  pBackGraph.fFindMinPaths(pTargetX,pTargetY);
  pBackGraph.fGetMinPath(pSourceX,pSourceY,pBackPath);
  pAvailable=pLimit-((pGoingPath.pCount-1)+(pBackPath.pCount-1));
  pBackGraph.fExpandPath(pBackPath,pAvailable);
  pSolution.fCopy(pProblem,pGoingPath,pBackPath);
  if(pSolution.pScore>pBestSolution.pScore) pBestSolution=pSolution;
  }

// fSolveBack: finds the best path for the back path
//   aDivisor:          this parameter specifies how long it should try to
//                      find solutions (the smaller values of aDivisor are
//                      faster than the larger values, but these usually find
//                      better solutions)
//   aFastLevel:        this parameter also helps finding solutions fast; it
//                      specifies when to ignore the aDivisor parameter (the
//                      larger values of aFastLevel are faster than the smaller
//                      values, but these usually find better solutions)
void                    tScenicTour::fSolveBack (int aDivisor,
                                                int aFastLevel)
  {

  pSegmentsCount=1;
  pSegments[0].pScore=pBackGraph.pNodesMap[pSourceX][pSourceY]->pMinDistance;
  pSegments[0].pMoves=pBackGraph.pNodesMap[pSourceX][pSourceY]->pMinMoves;
  pSegments[0].pPoint.pPosX=pTargetX;
  pSegments[0].pPoint.pPosY=pTargetY;
  pSegments[0].pPath.fClear();
  pSegments[1].pPoint.pPosX=pSourceX;
  pSegments[1].pPoint.pPosY=pSourceY;
  pSegments[1].pPath.fClear();
  fOptimize(aDivisor,aFastLevel);
  }

// fOptimize: optimizes a path by sub-dividing it in smaller segments
//            (used only for the longest path)
//   aDivisor:          same as aDivisor in fSolveBack
//   aFastLevel:        same as aFastLevel in fSolveBack
void                    tScenicTour::fOptimize  (int aDivisor,
                                                int aFastLevel)
  {
  int                   i,j,x,y,SrcX,SrcY,TgtX,TgtY;
  int                   Flag,Available,Score,Moves,DeltaScore,DeltaMoves;
  int                   BestX,BestY,BestScore,BestMoves,BestIndex;
  boolean               v;
  tNodePtr              node1,node2;
  static int            used[nMaxWidth][nMaxHeight];

  Flag=0;
  Available=pAvailable;
  for(x=0;x<pWidth;x++)
    for(y=0;y<pHeight;y++)
      used[x][y]=0;
  while((Available>0)&&(pSegmentsCount<nMaxSegments))
    {
    pBestPath1.fClear();
    pBestPath2.fClear();
    BestX=BestY=BestIndex=-1;
    BestScore=0;
    BestMoves=1;
    for(i=0;i<pSegmentsCount;i++)
      {
      Score=pSegments[i].pScore;
      Moves=pSegments[i].pMoves;
      SrcX=pSegments[i].pPoint.pPosX;
      SrcY=pSegments[i].pPoint.pPosY;
      TgtX=pSegments[i+1].pPoint.pPosX;
      TgtY=pSegments[i+1].pPoint.pPosY;
      pGraph1.fBuildNodes(pWidth,pHeight);
      pGraph2.fBuildNodes(pWidth,pHeight);
      pGraph1.fRemovePath(pGoingPath,False,False);
      pGraph2.fRemovePath(pGoingPath,False,False);
      for(j=0;j<pSegmentsCount;j++)
        {
        if(i==j) continue;
        pGraph1.fRemovePath(pSegments[j].pPath,j<i,j>i);
        pGraph2.fRemovePath(pSegments[j].pPath,j<i,j>i);
        }
      pGraph1.fBuildEdgesInv(pProblem,nTreshold);
      pGraph2.fBuildEdgesInv(pProblem,nTreshold);
      pGraph1.fFindMinPaths(SrcX,SrcY);
      pGraph2.fFindMinPaths(TgtX,TgtY);
      for(x=0;x<pWidth;x++)
        for(y=0;y<pHeight;y++)
          {
          if(((node1=pGraph1.pNodesMap[x][y])==NULL)
          ||((node2=pGraph2.pNodesMap[x][y])==NULL)
          ||((x==SrcX)&&(y==SrcY))||((x==TgtX)&&(y==TgtY)))
            continue;
          DeltaMoves=(node1->pMinMoves+node2->pMinMoves)-Moves;
          if((DeltaMoves<=Available/aDivisor)||(DeltaMoves>Available))
            continue;
          DeltaScore=(node1->pMinDistance+node2->pMinDistance)-Score;
          if(DeltaScore<=0) continue;
          if(Available<=aFastLevel)
            {
            if((DeltaScore<BestScore)||((DeltaScore==BestScore)&&(DeltaMoves>BestMoves)))
              continue;
            }
          else
            {
            if(((double) DeltaScore)/DeltaMoves<((double) BestScore)/BestMoves)
              continue;
            }
          pGraph1.fGetMinPath(x,y,pPath1);
          pGraph2.fGetMinPathInv(x,y,pPath2);
          Flag++;
          for(j=0;j<pPath1.pCount;j++)
            used[pPath1.pItems[j].pPosX][pPath1.pItems[j].pPosY]=Flag;
          for(j=1,v=False;j<pPath2.pCount;j++)
            if(used[pPath2.pItems[j].pPosX][pPath2.pItems[j].pPosY]==Flag)
              {
              v=True;
              break;
              }
          if(v) continue;
          BestX=x,BestY=y;
          BestScore=DeltaScore;
          BestMoves=DeltaMoves;
          BestIndex=i+1;
          pBestPath1=pPath1;
          pBestPath2=pPath2;
          }
      }
    if(BestIndex<0) break;
    for(j=++pSegmentsCount;j>BestIndex;j--) pSegments[j]=pSegments[j-1];
    pSegments[BestIndex].pScore=pProblem.fGetPathDistance(pBestPath2);
    pSegments[BestIndex].pMoves=pBestPath2.pCount-1;
    pSegments[BestIndex].pPoint.pPosX=BestX;
    pSegments[BestIndex].pPoint.pPosY=BestY;
    pSegments[BestIndex].pPath.fAssign(pBestPath2);
    pSegments[BestIndex-1].pScore=pProblem.fGetPathDistance(pBestPath1);
    pSegments[BestIndex-1].pMoves=pBestPath1.pCount-1;
    pSegments[BestIndex-1].pPath.fAssign(pBestPath1);
    Available-=BestMoves;
    pBackPath.fClear();
    for(i=0;i<pSegmentsCount;i++)
      {
      pBackPath.fAddPath(pSegments[i].pPath);
      if(i<pSegmentsCount-1) pBackPath.pCount--;
      }
    pBackGraph.fExpandPath(pBackPath,Available);
    pSolution.fCopy(pProblem,pGoingPath,pBackPath);
    if(pSolution.pScore>pBestSolution.pScore) pBestSolution=pSolution;
    }
  }

// main: program entry-point
//   argc:              the number of arguments to the program
//   argv:              the arguments to the program
int                     main                    (int argc,
                                                char* argv[])
  {

  Timer.fStart();                               // start the timer
  if(argc!=2) return 1;                         // correct number of arguments?
  ScenicTour=new tScenicTour;
  ScenicTour->fRead(argv[1]);                   // read input file
  ScenicTour->fSolve();                         // solve problem
  ScenicTour->fPrint();                         // print the solution
  delete ScenicTour;
  return 0;
  }