/* 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.		*/
/*
here is a (more or less) readable version of my program. I put
everything into one file, without stripping the comments and the debug
code (as I usually do before I send you my entry). Have mercy on me
about any spelling mistakes in the comments, since my english is lousy.

-- 
michael.strauch@cww.de
*/

/*  POTM ENTRY:  Everest                                            */
/*  My Name:   Michael Strauch                                      */
/*  My email:  michael.strauch@cww.de                               */
/*                                                                  */
/*  Compiler: gcc 2.7.2                                             */
/*  Compiling instructions:                                         */
/*  gcc -o Everest Everest.cc                                       */


// main.h
//
// global constants for each module
#ifndef MAIN_H
#define MAIN_H
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define DEBUG
// #define NDEBUG

#define FALSE 0
#define TRUE 1

typedef unsigned short USHORT;

#ifndef NDEBUG
#define assert(EXP) {if (!(EXP)){ \
   fprintf(stderr,"error in file %s, line %d\n", __FILE__, __LINE__);\
   Error("my assertion failed");}}
#else
#define assert(EXP)
#endif

// display error and stop program
void Error(char *);


#define max(a,b) ({int _a = (a), _b = (b); _a > _b ? _a : _b;})
#define min(a,b) ({int _a = (a), _b = (b); _a < _b ? _a : _b;})
#define abs(a) ({int _a = (a); _a >=0 ? _a : -_a;})

int checktime();
#ifdef DEBUG
# define MAXTIME 60
#endif
#ifndef DEBUG
# define MAXTIME 595
#endif

#endif

// grid.h
// 
// a grid contains the altitudes from the input file and data about
// used points
#ifndef GRID_H
#define GRID_H


struct Point
{
   short x,y;
   Point(){};
   Point(short _x,short _y):x(_x), y(_y){};
   operator==(const Point &p) const {return x== p.x && y==p.y;}
   operator!=(const Point &p) const {return x!= p.x || y!=p.y;}
};



int distmax(const Point &p1,const Point &p2);


class Grid
{
 public:
   enum {MAXHEIGHT=256, MAXWIDTH=256, MAXALTITUDE=256, MAXLIMIT=256*20};

 private:
   int height,width,limit;
   short altitude[MAXHEIGHT][MAXWIDTH];
   
 public:

   // construct grid from file
   Grid(const char *filename);

   // standard accessors
   int GetHeight() const {return height;}
   int GetWidth() const {return width;}
   int GetLimit() const {return limit;}
   int GetAltitude(int y,int x) const {return altitude[y][x];}
   int GetAltitude(const Point &p) const {return GetAltitude(p.y,p.x);}
   int DiffAltitude(const Point &p1, const Point &p2) const
     {return abs(altitude[p1.y][p1.x]-altitude[p2.y][p2.x]);}

   // find all neighbours of "p"
   int FindNeighbours(const Point &p,Point *pointarray) const;

   int MedianAltitudeDiff() const;
};

#endif

// path.h
//
// class for path lists
#ifndef PATH_H
#define PATH_H

// helper class
class PointSet
{
   USHORT points[Grid::MAXLIMIT];
   int size;

   Point IntToPoint(USHORT s) const{
      return Point(s&255,s>>8);
   }
   USHORT PointToInt(const Point &p) const{
      return p.x+(p.y<<8);
   }
 public:
   PointSet():size(0){};
   void Insert(const Point &p);
   void Delete(int idx);
   int Find(const Point &p);
   Point GetAt(int idx) const {
      assert(0<=idx && idx<size);
      return IntToPoint(points[idx]);
   }
   int GetSize() const{return size;}
};


// helper class, what kind of Insert or Remove was done
struct Move
{
   enum{INSERT,REMOVE,REPLACE,NOP};
   int id;
   Point point[2];
};


// PATH is implemented as a twodimensional array, containing a chain
// of points
class Path
{
 private:
   const Grid *myGrid;
   int limit; // limit for the length of the path
   int score; // sum of the altitude differences
   
   // unused points are encoded as zero (next=prev=NORTH)
   struct PointInfo{
      char next;
      char prev;
   };
   
   // encoded: is this point used,
   // direction of next point, direction of previous point
   PointInfo pointcode[Grid::MAXHEIGHT][Grid::MAXWIDTH];

   int length;                   // length of the path
   Point firstPoint,lastPoint;   // beginning and end of the path
   Point unblockedPoint;         // helper variables
   PointInfo unblockedPointInfo;
   PointSet removeablePoints;    // set of all removeable points
   PointSet allPoints;           // set of all points
   
   enum
{NORTH=0,NORTHEAST,EAST,SOUTHEAST,SOUTH,SOUTHWEST,WEST,NORTHWEST,NONE};

   // find out the direction from point p1 to point p2
   int direction(const Point &p1, const Point &p2) const;

   // adjust contents of "removeablePoints"
   void AdjustRemoveables(const Point &point);
   
 public:
   // find unused points that are neighbours to p / (p1,p2)
   // (returns number of points)
   int FindPointsAt(const Point &p,Point *pointarray) const;
   int FindPointsAt(const Point &p1,const Point &p2,Point *pointarray)
const;
 

   // construct a new path with first point (0,0)
   Path(const Grid &);

   // make a copy of "*this"
   Path &operator=(const Path &);
   
   // get access to the points of the path
   Point GetFirstPoint() const {return firstPoint;}
   Point GetLastPoint() const {return lastPoint;}
   Point GetNextPoint(const Point &p) const;
   Point GetPrevPoint(const Point &p) const;
   int GetLength() const {return length;}
   int GetLimit() const {return limit;}

   // insert a new point, or remove one, or replace one
   void Insert(const Point &p,const Point &newp);
   void Remove(const Point &);
   void Replace(const Point &p1, const Point &p2);
   
   // test if a point is used by the path
   bool IsPointUsed(const Point &p) const;
   // block a point for usage without inserting it
   void SetPointUsed(const Point &p);
     
   // test if a point can be removed
   bool IsPointRemoveable(const Point &p) const;
   // get list of all removable points
   void GetRemoveablePoints(Point *pointarray,int *size);
   // get number of removeable points
   int GetRemoveableCount() const  {return removeablePoints.GetSize();}
   // count number of removeables without influence on score
   int GetScorelessCount() const;
   // get n th removeable point
   Point GetNthRemoveable(int n) const {return
removeablePoints.GetAt(n);}
   // get n th point from pointset (not necessary in path order)
   Point GetNthPoint(int n) const {return allPoints.GetAt(n);}
   
   // get the set of points that can be inserted after "p" (up to 8)
   int GetInsertablePoints(const Point &p, Point *pointarray) const;
   
   // get the set of points p could be replaced with
   int GetReplacementPoints(const Point &p, Point *pointarray) const;

   // get the score of the current path
   int GetScore() const {return score;}
   // print the current path completely
   void Print() const;
   void PrintReverse() const;

   // do or undo one move
   void DoMove(const Move move);
   void ResetMove(const Move move);

};


#endif
// pathfinder.h
#ifndef PATHFINDER_H
#define PATHFINDER_H


class Grid;


// base class for Min/Max path finder classes
class PathFinder
{
 protected:
   const Grid *myGrid;
   
   // make path as short as possible
   void ShortenPath(Path*);
   // helper function
   int TripleAltDiff(const Point &p1, const Point &p2, const Point
&pnew);
   
 public:
   PathFinder(Grid *);

   // find a "good" path
   virtual Path *Find()=0;
};


// class for searching path with minimal score
class MinPathFinder:public PathFinder
{
 public:
   MinPathFinder(Grid *);

   virtual Path *Find();
};


// class for searching path with maximum score
class MaxPathFinder:public PathFinder
{
   Path usedPoints;  // points not to use any more

   // fill initial path
   void FindInitialPath(Path &path);
   // find next point for initial path
   Point FindNextInitialPoint (const Path &path, const Point &point);
 
   // helper functions: change path randomly by inserting or removing
one point
   // (returns FALSE if a change was not possible)
   // In "move", return the kind of action
   bool FindRandomInsert(Path *path,Move *move);
   bool FindRandomRemove(const Path *path,Move *move);
   bool FindRandomReplace(const Path *path,Move *move);

   bool IncreaseRandomly(Path *path);

   // find move combination, but do not change path
   // returns score of path, if moves will be applied
   int ChooseRandomMove(Path *path,Move *move,int *movecount);

 public:
   // do not use points on "minpath"
   MaxPathFinder(Grid *,Path *minpath);

   virtual Path *Find();
};


#endif
// main.cc
//
// program for the "Scenic"-POTM


#include <stdio.h>
#include <time.h>
#include <sys/times.h>

main(int argc, char **argv)
{
   if(argc<2)
     Error("too few parameters");

   // create input grid
   Grid *theGrid=new Grid(argv[1]);
   
   // find  path with minimal score
   MinPathFinder minfinder(theGrid);
   Path *minpath=minfinder.Find();
#ifdef DEBUG
   printf("minpath found, SHORT_SCORE=%d\n",minpath->GetScore());
#endif
   
   // find  path with maximal score
   MaxPathFinder maxfinder(theGrid,minpath);
   Path *maxpath=maxfinder.Find();
   
   // print path to stdout
   minpath->Print(); // for debug purposes
   maxpath->PrintReverse();
   
#ifdef DEBUG
   fprintf(stderr,"SHORT_SCORE=%d\n",minpath->GetScore());
   fprintf(stderr,"LONG_SCORE= %d\n",maxpath->GetScore());
   fprintf(stderr,"GRID_SCORE=
%10.3f\n",(double)maxpath->GetScore()/minpath->GetScore());
   fprintf(stderr,"Length=    
%d\n",minpath->GetLength()+maxpath->GetLength());

#endif
}



int checktime()
{
   static struct tms TMS;
   times(&TMS);
   /* This one works fine on Fred's computer only !!!              */
   /* add the elapsed system and user times                        */
   /* calculation comes out to the nearest second - rounded down   */
   return (TMS.tms_stime + TMS.tms_utime)/CLK_TCK;
}


// global error routine
void Error(char *string)
{
   fprintf(stderr,"%s\n", string);
   exit(1);
}
// grid.cc


Grid::Grid(const char *filename)
{
   FILE *file;
   int h,w,dummy;
   char line[100],c;
   
   file=fopen(filename,"r");
   if(!file){
      fputs("error - input file not found\n",stderr);
      exit(1);
   }
   
   fgets(line,99,file);
   fscanf(file,"%c%c%d",&c,&c,&limit);
   fscanf(file,"%d %d",&height,&width);
   fscanf(file,"%d",&dummy);
#ifdef DEBUG
   printf("Limit=%d, Height=%d, Width=%d\n",limit,height,width);
#endif   
   for(h=0;h<height;h++){
      for(w=0;w<width;w++){
         fscanf(file,"%hd",&altitude[h][w]);
      }
   }
   
   fclose(file);
}

int distmax(const Point &p1,const Point &p2)
{
   return max(abs(p1.x-p2.x),abs(p1.y-p2.y));
}

// find all neighbours of "p", store them in "nextPoints", return count
int Grid::FindNeighbours(const Point &p,Point *pointarray) const
{
   register int x,y,minx,maxx,miny,maxy,count;
   minx=max(p.x-1,0);
   maxx=min(p.x+1,width-1);
   miny=max(p.y-1,0);
   maxy=min(p.y+1,height-1);
   
   count=0;
   for(x=minx;x<=maxx;x++){
      for(y=miny;y<=maxy;y++){
         if(x==p.x && y==p.y) continue;
         pointarray[count].x=x;
         pointarray[count].y=y;
         count++;
      }
   }
   return count;
}

int Grid::MedianAltitudeDiff() const
{
   int x,y,i,count;
   int diffsum,diffcount;
   Point neighbours[8];
   
   diffsum=0;
   diffcount=0;
   for(x=0;x<width;x++){
     for(y=0;y<height;y++){
        Point p(x,y);
        count=FindNeighbours(p,neighbours);
        for(i=0;i<count;i++){
           diffsum+=DiffAltitude(p,neighbours[i]);
           diffcount++;
        }
     }
   }
   return diffsum/diffcount;
}
// path.cpp

// static helper arrays for finding coordinates to a direction
static int DirectionX[9]={ 0, 1, 1, 1, 0,-1,-1,-1,0};
static int DirectionY[9]={-1,-1, 0, 1, 1, 1, 0,-1,0};


// helper functions for point sets
void PointSet::Insert(const Point &p)
{
   register i,j,k;
   register USHORT code=PointToInt(p);

   assert(size<Grid::MAXLIMIT);
   
   // run binary search for "code"
   i=0;
   j=size;
   
   k=0;
   while(i<j){
      k=(i+j)>>1;
      if(points[k]==code)
        Error("PointSet::Insert - point already inserted");
      if(points[k]<code)
        i=k+1;
      else
        j=k;
   }
   // insert "code" at position "k"
#ifdef 0
   printf("PointSet::Insert, i=%d, size=%d, code=%d\n", i, size,
(int)code);
#endif
   memmove(points+i+1,points+i,(size-i)*sizeof(USHORT));
   points[i]=code;
   size++;
}

void PointSet::Delete(int idx)
{
   assert(0<=idx && idx<size);
#ifdef 0
   printf("PointSet::Delete, idx=%d, size=%d, code=%d\n", idx,
size,(int)points[idx]);
#endif

   memmove(points+idx,points+idx+1,(size-idx-1)*sizeof(USHORT));
   size--;
}

int PointSet::Find(const Point &p)
{
   register i,j,k;
   register USHORT code=PointToInt(p);
   
   // run binary search for "code"
   i=0;
   j=size;
   
#ifdef 0
   printf("PointSet::Find, code=%d\n", (int)code);
#endif
   while(i<j){
      k=(i+j)>>1;
      if(points[k]==code) return k;
      if(points[k]<code)
        i=k+1;
      else
        j=k;
   }
   return -1;
}

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

Path::Path(const Grid &g)
:myGrid(&g),length(0),firstPoint(Point(0,0)),lastPoint(Point(0,0))
{
   
   memset(pointcode,0,Grid::MAXHEIGHT*Grid::MAXWIDTH*sizeof(PointInfo));
   SetPointUsed(firstPoint);
   allPoints.Insert(firstPoint);
   
   limit=g.GetLimit();
   score=0;
}

// make a copy of "*this"
Path &Path::operator=(const Path &path)
{
   if(&path==this) return *this;
   
   myGrid=path.myGrid;
   length=path.length;
   firstPoint=path.firstPoint;
   lastPoint=path.lastPoint;
   limit=path.limit;
   score=path.score;
   removeablePoints=path.removeablePoints;
   allPoints=path.allPoints;
   memcpy(pointcode,path.pointcode,
          Grid::MAXHEIGHT*Grid::MAXWIDTH*sizeof(PointInfo));
   return *this;
}


// find out the direction from point p1 to point p2
// (points must be beneath each other)
int Path::direction(const Point &p1, const Point &p2) const
{
   int xdir=p2.x-p1.x;
   int ydir=p2.y-p1.y;
   switch (xdir*3+ydir){
    case -4: return NORTHWEST;
    case -3: return WEST;
    case -2: return SOUTHWEST;
    case -1: return NORTH;
    case  0: return NONE;
    case  1: return SOUTH;
    case  2: return NORTHEAST;
    case  3: return EAST;
    case  4: return SOUTHEAST;
      
    default: assert(FALSE); ;
   }
   return NONE;
}

Point Path::GetNextPoint(const Point &p) const
{
   // make sure "point" lies on path
   assert(IsPointUsed(p));
   
   PointInfo code=pointcode[p.y][p.x];
   assert(code.next<8);
   Point newp(p.x+DirectionX[code.next],p.y+DirectionY[code.next]);
   assert(newp.x>=0 && newp.x<myGrid->GetWidth() &&
          newp.y>=0 && newp.y<myGrid->GetHeight());

   return newp;
}

Point Path::GetPrevPoint(const Point &p) const
{
   // make sure "point" lies on path
   assert(IsPointUsed(p));
   
   PointInfo code=pointcode[p.y][p.x];
   assert(code.prev<8);
   Point newp(p.x+DirectionX[code.prev],p.y+DirectionY[code.prev]);
   assert(newp.x>=0 && newp.x<myGrid->GetWidth() &&
          newp.y>=0 && newp.y<myGrid->GetHeight());

   return newp;
}


// insert a new point after p
void Path::Insert(const Point &p,const Point &newp)
{
   // first, make sure that "newp" is not used, and that p belongs to
"this"
   assert(!IsPointUsed(newp) && IsPointUsed(p));
   
   // second, make sure that newp is beneath p and p.GetNextPoint();
   assert(distmax(p,newp)==1 &&
          (p==GetLastPoint() || distmax(GetNextPoint(p),newp)==1));

   // now insert "newp" into the path
   if(p!=GetLastPoint()){
      Point nextp=GetNextPoint(p);
      pointcode[newp.y][newp.x].next=direction(newp,nextp);
      pointcode[newp.y][newp.x].prev=direction(newp,p);
      pointcode[p.y][p.x].next=direction(p,newp);
      pointcode[nextp.y][nextp.x].prev=direction(nextp,newp);
      // adjust score
      score+=-myGrid->DiffAltitude(nextp,p)
        +myGrid->DiffAltitude(nextp,newp)
        +myGrid->DiffAltitude(newp,p);

      // adjust "removeablePoints" for nextp
      AdjustRemoveables(nextp);

   }else{
      pointcode[newp.y][newp.x].next=NONE;
      pointcode[newp.y][newp.x].prev=direction(newp,p);
      pointcode[p.y][p.x].next=direction(p,newp);
      lastPoint=newp;
      // adjust score
      score+=myGrid->DiffAltitude(newp,p);
   }
   length++;

   // adjust "removeablePoints" for p and newp
   AdjustRemoveables(p);
   removeablePoints.Insert(newp);

   allPoints.Insert(newp);
   
#ifdef 0
   for(int i=0;i<removeablePoints.GetSize();i++)
      assert(IsPointRemoveable(removeablePoints.GetAt(i)));
#endif

}


  
// remove a point from the current path
void Path::Remove(const Point &p)
{
   Point prevp,nextp;
   
   assert(IsPointUsed(p) && IsPointRemoveable(p));

   allPoints.Delete(allPoints.Find(p));
   
   // adjust removeable points for "p"
   removeablePoints.Delete(removeablePoints.Find(p));

   if(p==GetLastPoint()){
      prevp=GetPrevPoint(p);
      pointcode[prevp.y][prevp.x].next=direction(prevp,p);
      pointcode[p.y][p.x].next=0;
      pointcode[p.y][p.x].prev=0;
      lastPoint=prevp;
      score-= myGrid->DiffAltitude(p,prevp);
   }
   else{
      nextp=GetNextPoint(p);
      prevp=GetPrevPoint(p);
      pointcode[prevp.y][prevp.x].next=direction(prevp,nextp);
      pointcode[nextp.y][nextp.x].prev=direction(nextp,prevp);
      pointcode[p.y][p.x].next=0;
      pointcode[p.y][p.x].prev=0;

      // adjust score
      score+=myGrid->DiffAltitude(nextp,prevp)
-myGrid->DiffAltitude(nextp,p)
            -myGrid->DiffAltitude(p,prevp);

      // adjust removeable points for nextp;
      AdjustRemoveables(nextp);
   }
   length--;   

   // adjust removeable points for prevp
   AdjustRemoveables(prevp);

#ifdef 0
   for(int i=0;i<removeablePoints.GetSize();i++)
      assert(IsPointRemoveable(removeablePoints.GetAt(i)));
#endif

}

// replace point p1 by point p2
void Path::Replace(const Point &p1, const Point &p2)
{
   // first, make sure that "p1" can be replaced by p2
   assert(IsPointUsed(p1) && !IsPointUsed(p2));

   Point prevp(GetPrevPoint(p1));
   Point nextp(GetNextPoint(p1));
   assert(distmax(p2,prevp)==1 && distmax(p2,nextp)==1);
   
   pointcode[prevp.y][prevp.x].next=direction(prevp,p2);
   pointcode[nextp.y][nextp.x].prev=direction(nextp,p2);
   pointcode[p2.y][p2.x].next=direction(p2,nextp);
   pointcode[p2.y][p2.x].prev=direction(p2,prevp);;
   pointcode[p1.y][p1.x].next=0;
   pointcode[p1.y][p1.x].prev=0;

   // adjust score
   score+=myGrid->DiffAltitude(prevp,p2) +myGrid->DiffAltitude(nextp,p2)
         -myGrid->DiffAltitude(prevp,p1)
-myGrid->DiffAltitude(nextp,p1);

   // adjust removeable points
   AdjustRemoveables(nextp);
   AdjustRemoveables(prevp);
   AdjustRemoveables(p1);
   AdjustRemoveables(p2);

   allPoints.Delete(allPoints.Find(p1));
   allPoints.Insert(p2);
}


void Path::AdjustRemoveables(const Point &point)
{
   int idx=removeablePoints.Find(point);
   bool isremoveable=IsPointRemoveable(point);
   
   if(idx<0 && isremoveable)
     removeablePoints.Insert(point);
   else if(idx>=0 && !isremoveable)
     removeablePoints.Delete(idx);
}


// count number of removeables without influence on score
int Path::GetScorelessCount() const
{
   int i,count;
   
   count=0;
   for(i=0;i<removeablePoints.GetSize()-1;i++){
      Point p=removeablePoints.GetAt(i);
      Point prevp=GetPrevPoint(p);
      Point nextp=GetNextPoint(p);
      if(myGrid->DiffAltitude(prevp,p)+myGrid->DiffAltitude(p,nextp)==
         myGrid->DiffAltitude(prevp,nextp))
        count++;
   }
   return count;
}


// test if a point is used by the path
bool Path::IsPointUsed(const Point &p) const
{
   register PointInfo code=pointcode[p.y][p.x];
   return (code.next!=0) || (code.prev!=0);
}
   
// block point against further usage, decrease limit by one
void Path::SetPointUsed(const Point &p)
{
   PointInfo *pc=&pointcode[p.y][p.x];
   pc->next=NONE;
   pc->prev=NONE;
   
   limit--;
}


// test if a point can be removed
bool Path::IsPointRemoveable(const Point &p) const
{
   PointInfo pi=pointcode[p.y][p.x];
   register int d;
   register int next=pi.next;
   register int prev=pi.prev;
   
   if(next==NONE) return TRUE;
   if(prev==NONE) return FALSE;
   d=abs(next-prev);
   if(d==1 || d==7) return TRUE;
   if((next&1)==1 || (prev&1)==1) return FALSE;
   if(d==2 || d==6) return TRUE;
   return FALSE;
}

// find all removable points, do not include the last one
void Path::GetRemoveablePoints(Point *pointarray,int *size)
{
   register int count;
   register Point p,prev,next;
   
   count=0;
   p=GetFirstPoint();
   if(p!=GetLastPoint()){
      prev=p;
      p=GetNextPoint(p);
      while(p!=lastPoint){
         next=GetNextPoint(p);
         if(distmax(prev,next)==1)
           pointarray[count++]=p;
         prev=p;
         p=next;
      }
   }
   *size=count;  // return number of removeable points
}



// get the set of points that can be inserted after "p" (up to 8)
// (limit will not be checked !)
int Path::GetInsertablePoints(const Point &p, Point *pointarray) const
{
   if(p==GetLastPoint()) {
      // if p==lastPoint,  return every unused point around "p"
      return FindPointsAt(p,pointarray);
   }
   else{
      // return every unused point beneath p and GetNextPoint(p)
      return FindPointsAt(p,GetNextPoint(p),pointarray);
   }
}
   
// get the set of points that could replace "p"
int Path::GetReplacementPoints(const Point &p, Point *pointarray) const
{
   if(p==GetLastPoint() || p==GetFirstPoint())
     return 0;
   else
     return FindPointsAt(GetPrevPoint(p),GetNextPoint(p),pointarray);
}


// print the current path completely
void Path::Print() const
{
   Point p=GetFirstPoint();
   do{
      p=GetNextPoint(p);
      printf("%d %d\n",p.y,p.x);
   }
   while(p!=GetLastPoint());
}

// print the current path in reverse order
void Path::PrintReverse() const
{
   Point p=GetLastPoint();
   do{
      p=GetPrevPoint(p);
      printf("%d %d\n",p.y,p.x);
   }
   while(p!=GetFirstPoint());
}


// find unused points that are neighbours to p
int Path::FindPointsAt(const Point &p,Point *pointarray) const
{
   register size,x,y,minx,maxx,miny,maxy;
   minx=max(p.x-1,0);
   maxx=min(p.x+1,myGrid->GetWidth()-1);
   miny=max(p.y-1,0);
   maxy=min(p.y+1,myGrid->GetHeight()-1);
   
   size=0;
   for(x=minx;x<=maxx;x++){
      for(y=miny;y<=maxy;y++){
         Point np(x,y);
         if(IsPointUsed(np) || np==p)
           continue;
         pointarray[size++]=np;
      }
   }
   return size;
}

// find unused points that are neighbours to p1 and p2
int Path::FindPointsAt(const Point &p1,const Point &p2,Point
*pointarray) const
{
#define ADDPOINT  {if(!IsPointUsed(np)) pointarray[size++]=np;}

   int dx,dy;
   register size;
   register Point np;

   dx=abs(p1.x-p2.x);
   dy=abs(p1.y-p2.y);
   assert(dx<=2 && dy<=2);
   
   size=0;
   
   switch((dx<<2)+dy){  // special switch to increase speed
   //(a)  ****
   //     *x2*
   //     *1x*
   //     ****
    case 5:    // dx==1 && dy ==1
      np.x=p1.x;
      np.y=p2.y;
      ADDPOINT;
      np.x=p2.x;
      np.y=p1.y;
      ADDPOINT;
      break;

      //(b)  *xx*
      //     *12*
      //     *xx*
      //
    case 1: // dx==0 && dy==1
      if(p1.x>=1){
         np.x=p1.x-1;
         np.y=p1.y;
         ADDPOINT;
         np.y=p2.y;
         ADDPOINT;
      }
      if(p1.x+1<myGrid->GetWidth()){
         np.x=p1.x+1;
         np.y=p1.y;
         ADDPOINT;
         np.y=p2.y;
         ADDPOINT;
      }
      break;

    case 4:  // dx==1 && dy==0
      if(p1.y>=1){
         np.x=p1.x;
         np.y=p1.y-1;
         ADDPOINT;
         np.x=p2.x;
         ADDPOINT;
      }
      if(p1.y+1<myGrid->GetHeight()){
         np.x=p1.x;
         np.y=p1.y+1;
         ADDPOINT;
         np.x=p2.x;
         ADDPOINT;
      }
      break;

      //(c)  *x**
      //     1x2*
      //     *x**
    case 2: //dx==0 && dy==2
      np.y=(p1.y+p2.y)>>1;
      np.x=p1.x-1;
      if(np.x>=0)
        ADDPOINT;
      np.x++;
      ADDPOINT;
      np.x++;
      if(np.x<myGrid->GetWidth())
        ADDPOINT;
      break;

    case 8: // dx==2 && dy==0
      np.x=(p1.x+p2.x)>>1;
      np.y=p1.y-1;
      if(np.y>=0)
        ADDPOINT;
      np.y++;
      ADDPOINT;
      np.y++;
      if(np.y<myGrid->GetHeight())
        ADDPOINT;
      break;

   //(d)  *1x*
   //     **x2
   //     ****
    case 6: // dx==1 && dy==2
      np.y=(p1.y+p2.y)>>1;
      np.x=p1.x;
      ADDPOINT;
      np.x=p2.x;
      ADDPOINT;
      break;

    case 9: // dx==2 && dy==1
      np.x=(p1.x+p2.x)>>1;
      np.y=p1.y;
      ADDPOINT;
      np.y=p2.y;
      ADDPOINT;
      break;

      //(e)  1***
      //     *x**
      //     **2*
    case 10: //dx==2 && dy ==2
      np.x=(p1.x+p2.x)>>1;
      np.y=(p1.y+p2.y)>>1;
      ADDPOINT;
      break;

    default:;
      assert(FALSE);
      break;
   }
   return size;
}


// execute move on path
void Path::DoMove(const Move move)
{
   if(move.id==Move::REMOVE){
      Remove(move.point[0]);
   }
   else if (move.id==Move::INSERT) {
      Insert(move.point[0],move.point[1]);
   }
   else if(move.id==Move::REPLACE) {
      Replace(move.point[0],move.point[1]);
   }
}
// pathfinder.cpp


PathFinder::PathFinder(Grid *g)
:myGrid(g)
{
}


// **************************************************
// helper classes fpr finding the shortest path from upper left to
// lower right

struct HeapPoint
{
   Point point;
   int costs;
   int heapindex;
};

// class for finding the minimum costs for a path from Point(x,y) to 
// Point(gridsize-1,gridsize-1);
class CostFinder{
   const Grid *myGrid;
   int gridsize;
   HeapPoint HeapGrid[Grid::MAXHEIGHT][Grid::MAXWIDTH];
   HeapPoint *heap[Grid::MAXHEIGHT*Grid::MAXWIDTH];
   int heapsize;
   int pathlimit;   // maximum length of path (cuts spanning tree)
   
   // helper methods
   void swap_entries(int idx1,int idx2);
   void push_heap(int x,int y);
   Point pop_heap();
   void re_heap(int idx);
   int edgecosts(const Point &p1,const Point &p2) const;

 public:
   CostFinder(const Grid *grid);

   // run an algorithm to calculate the minimal costs
   void RunCalculation();
   
   // return resoult
   int GetCosts(int x,int y) const{
      return HeapGrid[x][y].costs;
   }
   int GetCosts(const Point &p) const{
      return HeapGrid[p.x][p.y].costs;
   }
   // return neighbour of "point" with minimum costs
   Point FindMinNeighbour(const Point &p) const;

};


CostFinder::CostFinder(const Grid *grid)
:myGrid(grid),gridsize(grid->GetHeight()),heapsize(0),pathlimit(grid->GetLimit()/2)
{
   int i,j;
   
   for(i=0;i<gridsize;i++){
      for(j=0;j<gridsize;j++){
         HeapGrid[i][j].costs=-1;
         HeapGrid[i][j].heapindex=-1;
         HeapGrid[i][j].point=Point(i,j);
      }
   }
}

void CostFinder::RunCalculation()
{
   int x,y,newcosts,costs,i,count;
   Point nextPoints[8];

   x=gridsize-1;
   y=x;
   
   HeapGrid[x][y].costs=0;
   push_heap(x,y);
   
   while(heapsize>0){
      Point p=pop_heap();   // find point with minimum costs
      costs=HeapGrid[p.x][p.y].costs;
#ifdef 0
      printf("x=%d, y=%d, costs=%d\n",p.x,p.y,costs);
#endif
      count=myGrid->FindNeighbours(p,nextPoints);
      for(i=0;i<count;i++){
         // calculate minimum costs to go to (x,y)
         newcosts=costs+edgecosts(nextPoints[i],p);
         x=nextPoints[i].x;
         y=nextPoints[i].y;
         // if maximum size of spanning tree is reached, stop
calculation
         if(max(x,y)+(newcosts&0xffff)>pathlimit)
           continue;

         if(HeapGrid[x][y].costs>newcosts || HeapGrid[x][y].costs<0){
            HeapGrid[x][y].costs=newcosts;
            // insert or replace entry in heap
            if(HeapGrid[x][y].heapindex<0)
              push_heap(x,y);
            else
              re_heap(HeapGrid[x][y].heapindex);
         }
      }
   }
#ifdef 0
   printf("Kostenmatrix:\n");
   for(x=0;x<gridsize;x++){
      printf("Zeile %d: ",x);
      for(y=0;y<gridsize;y++){
         printf("%d ", HeapGrid[x][y].costs>>16);
      }
      printf("\n");
   }
#endif
}

Point CostFinder::FindMinNeighbour(const Point &p) const
{
   int i,costs,count;
   Point nextPoints[8];
   
   // find an edge where the edge cost = cost difference
   count=myGrid->FindNeighbours(p,nextPoints);
   costs=GetCosts(p);
   for(i=0;i<count;i++){
      if(edgecosts(p,nextPoints[i])== costs-GetCosts(nextPoints[i]))
        break;
   }
   assert(i<count);
   
   return nextPoints[i];
}

// swap to entries of the heap, including adjustment of heapindex
void CostFinder::swap_entries(int idx1,int idx2)
{
   register HeapPoint *h1,*h2;

   assert(0<=idx1 && idx1<=heapsize && 0<=idx2 && idx2<=heapsize);

   h1=heap[idx1];
   h2=heap[idx2];
   heap[idx1]=h2;
   heap[idx2]=h1;
   h1->heapindex=idx2;
   h2->heapindex=idx1;

}

//  add HeapGrid[x][y] to the heap
void CostFinder::push_heap(int x,int y)
{
   heap[heapsize]=&HeapGrid[x][y];
   assert(heap[heapsize]->heapindex==-1);
   heap[heapsize]->heapindex=heapsize;
   re_heap(heapsize);

   heapsize++;
}

// take the minimum from the heap
Point CostFinder::pop_heap()
{
   Point p;
   register int idx,newidx,costs,leftcosts,rightcosts;
   
   // remember point at top of heap
   p=heap[0]->point;
   heap[0]->heapindex=-1;

   // re-balance heap
   heap[0]=heap[--heapsize];
   costs=heap[0]->costs;
   heap[0]->heapindex=0;
   idx=0;
   while(2*idx+2<heapsize){
      newidx=2*idx+1;
      leftcosts=heap[newidx]->costs;
      rightcosts=heap[newidx+1]->costs;
      assert(leftcosts>=0 && rightcosts >=0);

      if(costs<=min(leftcosts,rightcosts))break;  // stop if heap is
balanced
      if(leftcosts<rightcosts){
         swap_entries(idx,newidx);
         idx=newidx;
      }
      else{
         swap_entries(idx,newidx+1);
         idx=newidx+1;
      }
      
   }
   // re-balance last heap entry
   newidx=2*idx+1;
   if(newidx==heapsize){
      leftcosts=heap[newidx]->costs;
      if(costs>leftcosts)
        swap_entries(idx,newidx);
   }

   return p;
}

// rebalance heap, when the costs of heap[startidx] have become smaller
void CostFinder::re_heap(int startidx)
{
   register int idx,newidx,costs,newcosts;
   
   idx=startidx;
   costs=heap[idx]->costs;
   assert(heap[idx]->heapindex==idx);
   while(idx>0){
      newidx=(idx-1)/2;
      newcosts=heap[newidx]->costs;
      if(newcosts<=costs) break;  // stop if heap is balanced
      swap_entries(idx,newidx);
      idx=newidx;
   }
}

// return costs for an edge, only positive costs
int CostFinder::edgecosts(const Point &p1,const Point &p2) const
{
   return (abs(myGrid->GetAltitude(p1)-myGrid->GetAltitude(p2))<<16) +1;
}

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

MinPathFinder::MinPathFinder(Grid *g)
:PathFinder(g)
{
}

// find a new minimum path from top left to bottom right
Path *MinPathFinder::Find()
{
   // calculate the cost matrix
   CostFinder costmatrix(myGrid);
   costmatrix.RunCalculation();

   // now, use the cost matrix to find an optimal path
   Path *path=new Path(*myGrid);
   Point point=Point(0,0);

   // construct path from cost matrix
   while(point!=Point(myGrid->GetHeight()-1,myGrid->GetWidth()-1)){
      point=costmatrix.FindMinNeighbour(point);
      path->Insert(path->GetLastPoint(),point);
   }

   return path;
}


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

MaxPathFinder::MaxPathFinder(Grid *g, Path *minpath)
:PathFinder(g),usedPoints(*minpath)
{
}


Path *MaxPathFinder::Find()
{
   int score,bestscore,newscore,count,noimprovement;
   int threshold;
     
   // construct empty path object
   Path path(*myGrid),bestpath(*myGrid);

   int median=myGrid->MedianAltitudeDiff();

#ifdef DEBUG
   printf("Median altitude difference: %d\n", median);
#endif
   
   FindInitialPath(path);

#ifdef DEBUG
   printf("Score=%d, Length=%d, Removeables=%d\n",
          path.GetScore(), path.GetLength(), path.GetRemoveableCount());
#endif

   // change path randomly, try to increase the score
   count=1; 
   threshold=max(median,60);
   bestscore=path.GetScore();
   bestpath=path;
   noimprovement=0;
   while(checktime()<MAXTIME){
      // make some random change to "path"
      int movecount;
      Move move[2];
      score=path.GetScore();

      // find a possible combination of moves
      newscore=ChooseRandomMove(&path,move,&movecount);
      // if the moves will lead to a better path, apply them
      if(newscore>=score-threshold){
         for(int i=0;i<movecount;i++){
            path.DoMove(move[i]);
         }
         assert(path.GetScore()==newscore);
      }
      
#ifdef DEBUG
      if(count%(480000/myGrid->GetHeight())==0){
         printf("Score=%d, Best Score=%d, Count=%d, Length=%d,
Threshold=%d\n",
                path.GetScore(),bestscore,count,path.GetLength(),
threshold);
      }
#endif
      // remember path if new score is better than best score
      if(newscore>bestscore){
         noimprovement=0;
         bestpath=path;
         bestscore=newscore;
      }
      else{
         noimprovement++;
         if(noimprovement>40000 && threshold>0){
            threshold--;
            noimprovement=0;
         }
      }
      count++;
   }
   
#ifdef DEBUG
   fprintf(stderr,"COUNT=%d\n",count);
#endif
   return new Path(bestpath);
}

void MaxPathFinder::FindInitialPath(Path &path)
{
   Point point,endpoint;

   // block every used point
   for(point=usedPoints.GetFirstPoint();
       point!=usedPoints.GetLastPoint();
       point=usedPoints.GetNextPoint(point))
   {
      path.SetPointUsed(point);
   }
   
   // construct initial path without hitting any used points
   endpoint=Point(myGrid->GetHeight()-1,myGrid->GetWidth()-1);
   point=Point(0,0);
   while(point!=endpoint){
      point= FindNextInitialPoint(path,point);
      path.Insert(path.GetLastPoint(),point);
   }

   // *** greedy algorithm to extend path
   // *** (should be changed to make sure not to run in an endless loop)
   while(path.GetLength()<path.GetLimit()-5){
      IncreaseRandomly(&path);
   }
}


// try to increase score by randomly inserting one point
bool MaxPathFinder::IncreaseRandomly(Path *path)
{
   // first, find a place to insert
   register size,i,score,bestscore;
   Point pointarray[8],nextp,newp,bestp;

   if(path->GetLength()>=path->GetLimit())
     return FALSE;
   
   int pnum=rand()%path->GetLength();
   Point p=path->GetNthPoint(pnum);
   
   size=path->GetInsertablePoints(p,pointarray);
   if(size==0)
      return FALSE;
   
   nextp=path->GetNextPoint(p);

   // choose point that increases score most
   bestscore=-1;
   for(i=0;i<size;i++){
      newp=pointarray[i];
      score= TripleAltDiff(p,nextp,newp);
      assert(score>=0);
      if(score>bestscore){
         score=bestscore;
         bestp=newp;
      }
   }

   // do the insertion
   path->Insert(p,bestp);

   return TRUE;
}


// find next point for initial path
Point MaxPathFinder::FindNextInitialPoint (const Path &path, const Point
&point)
{
   int i,count;
   Point nextpoints[3];
   
   if(point.y==myGrid->GetHeight()-1){
      nextpoints[0]=Point(point.x+1,point.y);
      nextpoints[1]=Point(point.x+1,point.y-1);
      count=2;
   } else if(point.x==myGrid->GetWidth()-1){
      nextpoints[0]=Point(point.x,point.y+1);
      nextpoints[1]=Point(point.x-1,point.y+1);
      count=2;
   }
   else{
      nextpoints[0]=Point(point.x+1,point.y+1);
      nextpoints[1]=Point(point.x+1,point.y);
      nextpoints[2]=Point(point.x,point.y+1);
      count=3;
   }

   // choose point with highest difference in altitude
   Point bestp=Point(-1,-1);
   int bestdiff=-1;
   for(i=0;i<count;i++){
      Point p=nextpoints[i];
      if(path.IsPointUsed(p)) 
        continue;
      int diff=myGrid->DiffAltitude(p,point);
      if(diff>bestdiff){
         bestdiff=diff;
         bestp=p;
      }
   }
   assert(bestdiff>=0);
   return bestp;
}

// helper function: find a random place to insert one point
// ("move" contains information abount the result of the remove before,
//   and takes the insertion as result)
bool MaxPathFinder::FindRandomInsert(Path *path,Move *move)
{
   int size;
   Point pointarray[8];
   Point pnext;
   
   // return nothing if limit is reached
   if(path->GetLength()>path->GetLimit())
     return FALSE;
   
   Point p(path->GetNthPoint(rand()%path->GetLength()));
   
   if(move->id==Move::REMOVE && p==move->point[1])
     pnext=path->GetNextPoint(move->point[0]);
   else
     pnext=path->GetNextPoint(p);

   // find the points that are possible insertions
   size=path->FindPointsAt(p,pnext,pointarray);
   
   if(size==0){
      move->id=Move::NOP;
      return FALSE;
   }

   // choose one of the returned points
   Point pi(pointarray[rand()%size]);

   // return result
   move->id=Move::INSERT;
   move->point[0]=p;
   move->point[1]=pi;
   return TRUE;
}

                                       
// helper function: find a random point to remove
bool MaxPathFinder::FindRandomRemove(const Path *path,Move *move)
{
   int i,count;
   count=path->GetRemoveableCount();

   // do nothing if there is no removeable point
   if(count<=1){
      move->id=Move::NOP;
      return FALSE;
   }

   // choose one of the returned points
   i=rand()%(count-1);
   Point p=path->GetNthRemoveable(i);
   
   // remember result the action
   move->id=Move::REMOVE;
   move->point[0]=p;
   move->point[1]=path->GetPrevPoint(p);
   return TRUE;
}

// helper function: find a random point to replace
bool MaxPathFinder::FindRandomReplace(const Path *path,Move *move)
{
   register size;
   Point pointarray[8];
   
   Point p(path->GetNthPoint(rand()%path->GetLength()));
   
   // find the points that are possible insertions
   size=path->GetReplacementPoints(p, pointarray);
   
   if(size==0){
      move->id=Move::NOP;
      return FALSE;
   }

   // choose one of the returned points
   Point p2(pointarray[rand()%size]);

   // return result
   move->id=Move::REPLACE;
   move->point[0]=p;
   move->point[1]=p2;
   return TRUE;
}

// find move combination, but do not change path
// returns score of path, if moves will be applied
int MaxPathFinder::ChooseRandomMove(Path *path,Move *move,int
*movecount)
{
   int newscore=path->GetScore();
   int count=*movecount;
   Move m;
   m.id=Move::NOP;
   
   // decide whether to replace or to remove/insert
   if(rand()%3==0 && FindRandomReplace(path,&m)){
      move[0]=m;
      *movecount=1;
      Point prevp(path->GetPrevPoint(m.point[0]));
      Point nextp(path->GetNextPoint(m.point[0]));
      
      newscore+=-myGrid->DiffAltitude(prevp,m.point[0])
                -myGrid->DiffAltitude(nextp,m.point[0])
                +myGrid->DiffAltitude(prevp,m.point[1])
                +myGrid->DiffAltitude(nextp,m.point[1]);
      return newscore;
   }
   
   // look for remove opportunity
   count=0;
   if(path->GetLength()==path->GetLimit() || rand()%4>0){
      if(FindRandomRemove(path,&m)){
         move[count++]=m;
        
newscore-=TripleAltDiff(m.point[1],path->GetNextPoint(m.point[0]),
                                 m.point[0]);
      }
   }

   // now, look for an insert opportunity
   if(count>0 || path->GetLength()<path->GetLimit()){
      if(FindRandomInsert(path,&m)){
         // do not accept inserts at the remove position
         if(count==0 || (count>0 && move[0].point[0] != m.point[0] )){
            move[count++]=m;
            if(count==2 && move[0].point[1]== m.point[0]){
             
newscore+=TripleAltDiff(m.point[0],path->GetNextPoint(move[0].point[0]),
                                      m.point[1]);
            }
            else
             
newscore+=TripleAltDiff(m.point[0],path->GetNextPoint(m.point[0]),
                                      m.point[1]);
         }
      }
   }
   
   *movecount=count;
   return newscore;
}

// helper function to calculate the score difference when inserting or
// deleting a point
int PathFinder::TripleAltDiff(const Point &p1, const Point &p2, const
Point &pnew)
{
   return myGrid->DiffAltitude(p1,pnew)
         +myGrid->DiffAltitude(pnew,p2)
         -myGrid->DiffAltitude(p1,p2);
}