/* 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.		*/


/*  POTM ENTRY:  potmluck 					*/
/*  Your Name:   Michael Connelly				*/
/*  Your email:  mike_debra@yahoo.com				*/
/*  cc -o potmluck potmluck.c					*/

/****************************************************************\
 *	I had found this web site and was very interested in	*
 *	the competition but the contest was nearing the end,	*
 *	and I hadn't completely read the "rules". I had		*
 *	originally used lots of defines, long variable names,	*
 *	forward declaration of functions, comments, and few 	*
 *	global variables. When I read the 25k char limit I	*
 *	panicked and removed it all. 				*
\****************************************************************/

#include <stdio.h>
#include <math.h>
#include <malloc.h>
#include <unistd.h>
#include <sys/times.h>
#define MAXTIME		560
#define MAX_SIZE	255

typedef unsigned char	AltArrayType[MAX_SIZE][MAX_SIZE];

typedef struct {
	int		Limit;
	unsigned char	Width;
	unsigned char	Height;
	unsigned char	MaxAlt;
	AltArrayType	AltArray;
	AltArrayType	WeightArray;
	AltArrayType	UsedArray;
}	TIStruct;

typedef struct {
	unsigned char	Row;
	unsigned char	Col;
} RowColStruct;

typedef struct {
	RowColStruct	RCArray[MAX_SIZE*20];
	int		RCQty;
	long		PathTotal;
} PathStruct;

/****************************************************************\
 * The following are arrays containing paths for short and long.*
 * SPArrayPtr is the Short Path Array				*
 * LPArrayPtr is the Long Path Array				*
 * BPArrayPtr is the Backward Long Path Array			*
\****************************************************************/
PathStruct		*SPArrayPtr = NULL;
int			SPArrayQty = 0;
int			SPArrayAlloced = 0;

PathStruct		*LPArrayPtr = NULL;
int			LPArrayQty = 0;
int			LPArrayAlloced = 0;

PathStruct		*BPArrayPtr = NULL;
int			BPArrayQty = 0;
int			BPArrayAlloced = 0;

PathStruct		BestLPath;
int			BestLPathSet = 0;

int		CurrentMinimize;
unsigned char	CToRow, CToCol;
long		COLeaf = 0;
PathStruct	COPath;

TIStruct	TourInfo;
AltArrayType	SaveUsedArray, SaveWeightArray;

void
PrintPath(PSPtr)
	PathStruct	*PSPtr;
{
	int	I;
	
	for (I = 1; I < PSPtr->RCQty; I++)
		printf("%d %d\n", (int)PSPtr->RCArray[I].Row,
(int)PSPtr->RCArray[I].Col);
}

void
ReversePath(PSPtr)
	PathStruct	*PSPtr;
{
	RowColStruct	Temp;
	int		I;
	
	for (I = 0; I < PSPtr->RCQty/2; I++) {
		Temp = PSPtr->RCArray[I];
		PSPtr->RCArray[I] = PSPtr->RCArray[PSPtr->RCQty-1-I];
		PSPtr->RCArray[PSPtr->RCQty-1-I] = Temp;
	}
}

void
PrintAnswer(ShortPath, LongPath)
	PathStruct	*ShortPath, *LongPath;
{
	PrintPath(ShortPath);
	PrintPath(LongPath);
}

int
checktime()
{
	int seconds;
	static struct tms TMS;
	static int	ClkTck=0;

	times(&TMS);
	if (!ClkTck)
		ClkTck = (int)sysconf(_SC_CLK_TCK);
	seconds = (TMS.tms_stime + TMS.tms_utime)/ClkTck ;
	if (seconds >= MAXTIME) {
		PrintAnswer(SPArrayPtr, &BestLPath);
		exit(0);
	}
	return(seconds >= (MAXTIME/2));
}

void
LoadFileInfo(FileName, TIPtr)
	char		*FileName;
	TIStruct	*TIPtr;
{
	FILE		*FPtr;
	unsigned char	Row = 0, Col = 0;
	char		Dummy[255];
	int		IntDummy;
	
	if ((FPtr = fopen(FileName, "r")) == NULL) {
		fprintf(stderr, "File not found : %s\n", FileName);
		exit(0);
	}
	fscanf(FPtr, "%s", Dummy);
	fscanf(FPtr, "%s", Dummy);
	fscanf(FPtr, "%d", &(TIPtr->Limit));
	fscanf(FPtr, "%d", &IntDummy);
	TIPtr->Width = (unsigned char)IntDummy;
	fscanf(FPtr, "%d", &IntDummy);
	TIPtr->Height = (unsigned char)IntDummy;
	fscanf(FPtr, "%d", &IntDummy);
	TIPtr->MaxAlt = (unsigned char)IntDummy;
	while (fscanf(FPtr, "%d", &IntDummy) != EOF) {
		TIPtr->AltArray[Row][Col] = (unsigned char)IntDummy;
		if (Col == (TIPtr->Width-1)) {
			Row++;
			Col = 0;
		}
		else
			Col++;
	}
	fclose(FPtr);
}

int
Distance(Row1, Col1, Row2, Col2)
	int	Row1, Col1, Row2, Col2;
{
	int	RowDist, ColDist;

	RowDist = abs(Row1 - Row2);
	ColDist = abs(Col1 - Col2);
	return(RowDist > ColDist ? RowDist : ColDist);
}				

int
DeltaAlt(Row1, Col1, Row2, Col2)
	int	Row1, Col1, Row2, Col2;
{
	return(abs ((int)TourInfo.AltArray[Row1][Col1] -
(int)TourInfo.AltArray[Row2][Col2]));
}				

int
OffsetAlt(PSPtr, FO, TO)
	PathStruct	*PSPtr;
	int		FO, TO;
{
	return(DeltaAlt(PSPtr->RCArray[FO].Row, PSPtr->RCArray[FO].Col, 
			PSPtr->RCArray[TO].Row, PSPtr->RCArray[TO].Col));
}

void
AddPointToArray(RCArray, RCQty, Row, Col)
	RowColStruct	*RCArray;
	int		*RCQty;
	int		Row, Col;
{
	RCArray[*RCQty].Row = (unsigned char)Row;
	RCArray[*RCQty].Col = (unsigned char)Col;
	(*RCQty)++;
}
int
GetPointsAroundPoint(Row, Col, RCArray, RCQty)
	int		Row, Col;
	RowColStruct	RCArray[];
	int		*RCQty;
{
	int	I, J;

	for (I = -1; I <= 1; I++)
		for (J = -1; J <= 1; J++)
			if ((I || J) && ValidRowColInt(Row+I, Col+J) )
				AddPointToArray(RCArray, RCQty, Row+I, Col+J);
	return(*RCQty);
}

void
CalcWeightForPoint(Row, Col)
	int		Row, Col;
{
	int		PointTotal=0, Point;
	RowColStruct	RCArray[8];
	int		RCQty=0;

	GetPointsAroundPoint(Row, Col, RCArray, &RCQty);
	for (Point = 0; Point < RCQty; Point++)
		if (!TourInfo.UsedArray[RCArray[Point].Row][RCArray[Point].Col])
			PointTotal += DeltaAlt(Row, Col, (int)RCArray[Point].Row,
(int)RCArray[Point].Col);
	TourInfo.WeightArray[(unsigned char)Row][(unsigned char)Col] =
(unsigned char)(PointTotal / RCQty);
}

void
RecalculatePointsAroundOnePoint(Row, Col)
	int		Row, Col;
{
	int		Point;
	RowColStruct	RCArray[8];
	int		RCQty=0;

	GetPointsAroundPoint(Row, Col, RCArray, &RCQty);
	for (Point = 0; Point < RCQty; Point++)
		CalcWeightForPoint(RCArray[Point].Row, RCArray[Point].Col);
}

void
RecalcWeight()
{
	int		Row, Col;

	for (Row = 0; Row < (int)TourInfo.Height; Row++) 
		for (Col = 0; Col < (int)TourInfo.Width; Col++) 
			CalcWeightForPoint(Row, Col);
}

void
CalcFileInfo()
{
	memset(TourInfo.UsedArray, 0, sizeof(TourInfo.UsedArray));
	RecalcWeight();
}

PathStruct
*GetNewPathPtr(PathArrayPtr, PathArrayQty, PathArrayAlloced)
	PathStruct	**PathArrayPtr;
	int		*PathArrayQty, *PathArrayAlloced;
{
	if ((*PathArrayQty) + 1 > (*PathArrayAlloced)) {
		(*PathArrayAlloced) += MAX_SIZE * 2;
		if (*PathArrayPtr)
			*PathArrayPtr = (PathStruct *) realloc(PathArrayPtr,
(*PathArrayAlloced) * sizeof(PathStruct));
		else
			*PathArrayPtr = (PathStruct *) malloc((*PathArrayAlloced) *
sizeof(PathStruct));
	}
	memset((*PathArrayPtr)+(*PathArrayQty), 0, sizeof(PathStruct));
	(*PathArrayQty)++;
	return((*PathArrayPtr)+(*PathArrayQty)-1);
}


void
AddToPath(PSPtr, Row, Col)
	PathStruct	*PSPtr;
	unsigned char	Row, Col;
{
	PSPtr->RCArray[PSPtr->RCQty].Row = Row;
	PSPtr->RCArray[PSPtr->RCQty].Col = Col;
	(PSPtr->RCQty)++;
}

void
AddPointsToPath(PSPtr, RowStart, ColStart, RowDir, ColDir, NumPoints)
	PathStruct	*PSPtr;
	unsigned char	RowStart, ColStart, NumPoints;
	int		RowDir, ColDir;
{
	unsigned char	Point;

	for (Point = 0; Point < NumPoints; Point++)
		AddToPath(PSPtr, (unsigned char)((int)RowStart+(Point*RowDir)),
				(unsigned char)((int)ColStart+(Point*ColDir)));
}

void
CalcWeightOfPath(PSPtr)
	PathStruct	*PSPtr;
{
	int	I;
	
	PSPtr->PathTotal = 0;
	for (I = 0; I < (PSPtr->RCQty)-1; I++)
		PSPtr->PathTotal += OffsetAlt(PSPtr, I, I+1);
}

void
MirrorPath(Ptr1, Ptr2)
	PathStruct	*Ptr1, *Ptr2;
{
	int	I;

	for (I = 0; I < Ptr1->RCQty; I++) {
		Ptr2->RCArray[I].Row = Ptr1->RCArray[I].Col;
		Ptr2->RCArray[I].Col = Ptr1->RCArray[I].Row;
	}
	Ptr2->RCQty = Ptr1->RCQty;
}

int
PathTotalCompareFormula(ptr1, ptr2)
	PathStruct	*ptr1, *ptr2;
{
	double	Amt1, Amt2;
	
	Amt1 = (double)ptr1->PathTotal / (double)(TourInfo.Limit -
ptr1->RCQty + 1);
	Amt2 = (double)ptr2->PathTotal / (double)(TourInfo.Limit -
ptr2->RCQty + 1);
	if (Amt1 > Amt2)
		return(1);
	if (Amt2 > Amt1)
		return(-1);
	return(ptr1->RCQty - ptr2->RCQty);
}

void
SortShortPaths(PSPtr, PathStructQty)
	PathStruct	*PSPtr;
	int		PathStructQty;
{
	if (PathStructQty > 1)
		qsort(PSPtr, PathStructQty, sizeof(PathStruct),
PathTotalCompareFormula);
}

void
SLMassage(PSPtr, PathStructQty, LongTest)
	PathStruct	**PSPtr;
	int		*PathStructQty, LongTest;
{
	int	I;
	long	Last;
	
	for (I = 0; I < *PathStructQty; I++) {
		CalcWeightOfPath((*PSPtr)+I);
		do {
			Last = (*PSPtr)[I].PathTotal;
			MassageSL((*PSPtr)+I, 1);
			CalcWeightOfPath((*PSPtr)+I);
			if (checktime())
				return;
		} while (LongTest && (*PSPtr)[I].PathTotal < Last);
	}
}

void
CalcWeightOfAllPaths(PSPtr, PathStructQty)
	PathStruct	*PSPtr;
	int		PathStructQty;
{
	int	I;
	
	for (I = 0; I < PathStructQty; I++)
		CalcWeightOfPath(PSPtr+I);
}

/****************************************************************\
 * Unfortunately I thought Dijkstra used to play for the Mets.	*
 * The idea here is to to find the best path that gets to the	*
 * destination without using backward or sideways movement.	*
 * First generate all paths  as n goes from 0 to width which 	*
 * traverse the edge for N, then the diagonal, then the other	*
 * edge for N. A mirror function transposes the points so that	*
 * the other half doesn't have to be generated. These paths are	*
 * then minimized and sorted to find the best path.		*
\****************************************************************/
void
ShortestPath()
{
	PathStruct	*PSPtr, *MirrorPtr;
	unsigned char	N;
	
	PSPtr = GetNewPathPtr(&SPArrayPtr, &SPArrayQty, &SPArrayAlloced);
	AddPointsToPath(PSPtr, 0, 0, 1, 1, TourInfo.Width);
	CalcWeightOfPath(PSPtr);
	for (N = 1; N < TourInfo.Width-2; N++) {
		PSPtr = GetNewPathPtr(&SPArrayPtr, &SPArrayQty, &SPArrayAlloced);
		AddPointsToPath(PSPtr, 0, 0, 0, 1, N+1);
		AddPointsToPath(PSPtr, 1, N+1, 1, 1, TourInfo.Width-2-N);
		AddPointsToPath(PSPtr, TourInfo.Width-1-N, TourInfo.Width-1, 1, 0,
N+1);
		CalcWeightOfPath(PSPtr);
		MirrorPtr = GetNewPathPtr(&SPArrayPtr, &SPArrayQty, &SPArrayAlloced);
		MirrorPath(PSPtr, MirrorPtr);
		CalcWeightOfPath(MirrorPtr);
	}
	CalcWeightOfAllPaths(SPArrayPtr, SPArrayQty);
	SortShortPaths(SPArrayPtr, SPArrayQty);
	SLMassage(&SPArrayPtr, &SPArrayQty, 0);
	CalcWeightOfAllPaths(SPArrayPtr, SPArrayQty);
	SortShortPaths(SPArrayPtr, SPArrayQty);
}

int
ValidRowColInt(Row, Col)
	int		Row, Col;
{
	return( (Row >=0) && (Row < TourInfo.Height) && (Col >=0) && (Col <
TourInfo.Width)); 
}

int	CurrentRange;
int	MaxRange = 20;
int	OffsetAdj;

void
AddToWeightByFactor(PointWeight, Factor, ReturnVal)
	double	PointWeight, Factor, *ReturnVal;
{
	*ReturnVal = ((*ReturnVal * Factor) + PointWeight) / (Factor + 1.0);
}

void
AdjWeightFormula(PointWeight, NumPoints, Distance, Offset, ReturnVal)
	double	PointWeight;
	int	NumPoints, Distance, Offset;
	double	*ReturnVal;
{
	
	PointWeight /= 5.0;
	PointWeight *= PointWeight;
	PointWeight /= Distance;
	if (OffsetAdj)
		PointWeight /= (Offset+1);
	AddToWeightByFactor(PointWeight, (double)NumPoints, ReturnVal);
}

int
AddWForRC(Row, Col, Added, D, Offset, ReturnVal)
	int		Row, Col, *Added, D, Offset;
	double		*ReturnVal;
{
	if (!ValidRowColInt(Row, Col))
		return(0);
	if (TourInfo.UsedArray[(unsigned char)Row][(unsigned char)Col] == 1)
		AdjWeightFormula(0.0, (*Added)++, D, Offset, ReturnVal);
	else
		AdjWeightFormula((double) TourInfo.WeightArray[(unsigned
char)Row][(unsigned char)Col],
				(*Added)++, D, Offset, ReturnVal);
	return(1);
}

/****************************************************************\
 * This is the heart of the long path section. Treat each point	*
 * as a gravity point. Its weight is the average of the 	*
 * difference of all points around it. This function attempts	*
 * to gravitate in the right direction				*
\****************************************************************/
int
CalcValueInDirection(StartRow, StartCol, AdjRow, AdjCol, ReturnVal)
	unsigned char	StartRow, StartCol;
	int		AdjRow, AdjCol;
	double		*ReturnVal;
{
	int	Row, Col, LRow, LCol, Distance, Added=0, I, NLP, RangeAdj;
	
	*ReturnVal = 0.0;
	Row = (int)StartRow + AdjRow;
	Col = (int)StartCol + AdjCol;
	if (TourInfo.UsedArray[(unsigned char)Row][(unsigned char)Col] == 1)
		return(0);
	if (!AddWForRC(Row, Col, &Added, 1, 0, ReturnVal))
		return(0);
	for (Distance = 2; Distance < CurrentRange; Distance++) {
		Row = (int)StartRow + (AdjRow * Distance);
		Col = (int)StartCol + (AdjCol * Distance);
		if (!ValidRowColInt(Row, Col))
			return(1);
		AddWForRC(Row, Col, &Added, 2, 0, ReturnVal);
		if (Distance <= (CurrentRange / 2))
			NLP = Distance / 2;
		else
			NLP = (CurrentRange - Distance) / 2;
		for (I = 1; I <= NLP; I++) {
			if (AdjRow && AdjCol) {	
				AddWForRC(Row - (AdjRow * I), Col, &Added, Distance, I, ReturnVal);
				AddWForRC(Row, Col - (AdjCol * I), &Added, Distance, I, ReturnVal);
			}
			else {
				AddWForRC(Row + (AdjCol * I), Col + (AdjRow * I), &Added,
Distance, I, ReturnVal);
				AddWForRC(Row - (AdjCol * I), Col - (AdjRow * I), &Added,
Distance, I, ReturnVal);
			}
		}
	}
	return(1);
}

int
CheckNextPoint(StartRow, StartCol, AdjRow, AdjCol, NextRow, NextCol,
HighestValue, ReturnVal)
	unsigned char	StartRow, StartCol;
	int		AdjRow, AdjCol;
	int		*NextRow, *NextCol;
	double		*HighestValue, *ReturnVal;
{
	if (CalcValueInDirection(StartRow, StartCol, AdjRow, AdjCol,
ReturnVal)) {
		if (*ReturnVal > *HighestValue) {
			*HighestValue = *ReturnVal;
			*NextRow = (int)StartRow + AdjRow;
			*NextCol = (int)StartCol + AdjCol;
			return(1);
		}
	}
	return(0);
}

#define	PATH_ENDED	2

int
GetNextPoint(PSPtr, StartRow, StartCol, EndRow, EndCol, NextRow,
NextCol, MovesLeft)
	PathStruct	*PSPtr;
	unsigned char	StartRow, StartCol, EndRow, EndCol;
	int		*NextRow, *NextCol, MovesLeft;
{
	int	I, J, TotalDistance, NextDistance, NumAdded=0;
	double	ReturnVal, HighestValue = -1.0;

	TotalDistance = Distance((int)StartRow, (int)StartCol, (int)EndRow,
(int)EndCol);
	if (TotalDistance >= (MovesLeft-(TourInfo.Width/7)))
		return(AddMinimumPathToPath(PSPtr, StartRow, StartCol, EndRow,
EndCol, 0) ? PATH_ENDED : 0);
	for (I = -1; I <= 1; I++)
		for (J = -1; J <= 1; J++)
			if ((I || J) && ValidRowColInt((int)StartRow+I, (int)StartCol+J) ) {
				NextDistance = Distance((int)StartRow+I, (int)StartCol+J,
(int)EndRow, (int)EndCol);
				if (MovesLeft > NextDistance)
					NumAdded += CheckNextPoint(StartRow, StartCol, I, J, NextRow,
NextCol, &HighestValue, &ReturnVal);
			}
	if (!NumAdded)
		return(AddMinimumPathToPath(PSPtr, StartRow, StartCol, EndRow,
EndCol, 0) ? PATH_ENDED : 0);
	return(1);
}

int	MaxLoop = 10;

int
GoBack(PSPtr, EndRow, EndCol)
	PathStruct	*PSPtr;
	unsigned char	EndRow, EndCol;
{
	int	I;
	
	for (I = 1; I < MaxLoop; I++) {
		TourInfo.UsedArray[PSPtr->RCArray[PSPtr->RCQty-1].Row]
				[PSPtr->RCArray[PSPtr->RCQty-1].Col] = 0;
		PSPtr->RCQty--;
		if (AddMinimumPathToPath(PSPtr, PSPtr->RCArray[PSPtr->RCQty-1].Row,
			PSPtr->RCArray[PSPtr->RCQty-1].Col, EndRow, EndCol, 0)) {
			return(1);
		}
	}
	return(0);
}

int
PointTest(PSPtr, MaxLength, EndRow, EndCol)
	PathStruct	*PSPtr;
	int		MaxLength;
	unsigned char	EndRow, EndCol;
{
	unsigned char	Row, Col;
	int		Counter = 0, NextRow, NextCol, ReturnVal;
	int		DoMass=1;
	
	while (PSPtr->RCQty <= MaxLength) {
		if (!(ReturnVal = GetNextPoint(PSPtr,
PSPtr->RCArray[PSPtr->RCQty-1].Row, 
			PSPtr->RCArray[PSPtr->RCQty-1].Col, EndRow, EndCol,
			&NextRow, &NextCol, MaxLength - PSPtr->RCQty + 1))) {
			if (DoMass) {
				MassageSL(PSPtr, 0);
				DoMass = 0;
			}
			else
				return(GoBack(PSPtr, EndRow, EndCol));
		}
		else {
			if (ReturnVal == PATH_ENDED)
				return(1);
			AddToPath(PSPtr, (unsigned char)NextRow, (unsigned char)NextCol);
			TourInfo.UsedArray[(unsigned char)NextRow][(unsigned char)NextCol]
= 1;
			if ((NextRow == (int)EndRow) && (NextCol == (int)EndCol))
				return(1);
			if (PSPtr->RCQty > 2)
				RecalculatePointsAroundOnePoint(PSPtr->RCArray[PSPtr->RCQty-2].Row,
				PSPtr->RCArray[PSPtr->RCQty-2].Col);
		}
		if (++Counter > (MaxLength * 2))
			return(0);
	}
	return(0);
}

void
SetUsedArrayLoop(PSPtr, From, To, OnOff)
	PathStruct	*PSPtr;
	int		From, To;
	unsigned char	OnOff;
{
	int	I;

	for (I = From; I <= To; I++) 
		TourInfo.UsedArray[PSPtr->RCArray[I].Row][PSPtr->RCArray[I].Col] =
OnOff;
}

void
InitUsedAndWeightFromPath(PSPtr)
	PathStruct	*PSPtr;
{
	int	I;

	memset(TourInfo.UsedArray, 0, sizeof(TourInfo.UsedArray));
	SetUsedArrayLoop(PSPtr, 1, PSPtr->RCQty-2, 1);
	RecalcWeight();
	memcpy(SaveUsedArray, TourInfo.UsedArray, sizeof(SaveUsedArray));
	memcpy(SaveWeightArray, TourInfo.WeightArray, sizeof(SaveWeightArray));
}

void
RestoreUsedAndWeight()
{
	memcpy(TourInfo.UsedArray, SaveUsedArray, sizeof(TourInfo.UsedArray));
	memcpy(TourInfo.WeightArray, SaveWeightArray,
sizeof(TourInfo.WeightArray));
}

int
OffsetDistance(PSPtr, FO, TO)
	PathStruct	*PSPtr;
	int		FO, TO;
{
	return(Distance((int)PSPtr->RCArray[FO].Row,
(int)PSPtr->RCArray[FO].Col, 
			(int)PSPtr->RCArray[TO].Row, (int)PSPtr->RCArray[TO].Col));
}

int
FindShortPoint(PSPtr, BV)
	PathStruct	*PSPtr;
	int		*BV;
{
	int	I, SO=0, Value;
	
	for (I = 1; I < PSPtr->RCQty-2; I++) 
		if (OffsetDistance(PSPtr, I-1, I+1) == 1) {
			Value = OffsetAlt(PSPtr, I-1, I) + OffsetAlt(PSPtr, I, I+1) -
OffsetAlt(PSPtr, I-1, I+1);
			if (!SO || (Value < *BV)) {
				*BV = Value;
				SO = I;
			}
		}
	return(SO);
}


#define		_GetRow(P, I)		(P->RCArray[I].Row)
#define		_GetCol(P, I)		(P->RCArray[I].Col)

int
ValidMove(Row, Col)
	int	Row, Col;
{
	return(ValidRowColInt(Row, Col) && !TourInfo.UsedArray[(unsigned
char)Row][(unsigned char)Col]);
}

int
FindNewPoint(PSPtr, BV, BR, BC)
	PathStruct	*PSPtr;
	int		*BV, *BR, *BC;
{
	int	P, I, J, NR, NC, SO=0, Value;
	
	for (P = 0; P < PSPtr->RCQty-2; P++)
		for (I = -1; I <= 1; I++)
			for (J = -1; J <= 1; J++)
				if (I || J) {
					NR = (int)_GetRow(PSPtr, P)+I;
					NC = (int)_GetCol(PSPtr, P)+J;
					if (ValidMove(NR, NC) && (Distance(NR, NC, (int)_GetRow(PSPtr,
P+1), (int)_GetCol(PSPtr, P+1)) == 1)) {
						Value =  DeltaAlt((int)_GetRow(PSPtr, P), (int)_GetCol(PSPtr, P)
,NR, NC) +
							DeltaAlt(NR, NC, (int)_GetRow(PSPtr, P+1), (int)_GetCol(PSPtr,
P+1)) -
							OffsetAlt(PSPtr, P, P+1);
						if (!SO || (Value > *BV)) {
							*BV = Value;
							SO = P;
							*BR = NR;
							*BC = NC;
						}
					}
				}
	return(SO);
}

int
AddBestPoint(PSPtr, BHV)
	PathStruct	*PSPtr;
	int		*BHV;
{
	int	P, I, BR, BC;
	
	P = FindNewPoint(PSPtr, BHV, &BR, &BC);
	if (*BHV) {
		TourInfo.UsedArray[(unsigned char)BR][(unsigned char)BC] = 1;
		for (I = PSPtr->RCQty; I > (P+1); I--)
			PSPtr->RCArray[I] = PSPtr->RCArray[I-1];
		PSPtr->RCArray[P+1].Row = (unsigned char)BR;
		PSPtr->RCArray[P+1].Col = (unsigned char)BC;
		PSPtr->RCQty++;
		return(1);
	}
	return(0);
}

/****************************************************************\
 * Remove bad points and add good ones.	(long path only)	*
\****************************************************************/
void
MassageSP(PSPtr)
	PathStruct	*PSPtr;
{
	int	P, I=1, BLV=0, BHV=0, BR, BC, Counter=0;
	
	while ( I && (PSPtr->RCQty < (TourInfo.Limit - SPArrayPtr->RCQty + 2)))
		I = AddBestPoint(PSPtr, &BHV);	
	do {
		if (P = FindShortPoint(PSPtr, &BLV)) {
			TourInfo.UsedArray[_GetRow(PSPtr, P)][_GetCol(PSPtr, P)] = 0;
			for (I = P; I < PSPtr->RCQty-1; I++)
				PSPtr->RCArray[I] = PSPtr->RCArray[I+1];
			PSPtr->RCQty--;
		}
		else
			return;
		AddBestPoint(PSPtr, &BHV);
	} while ((BHV > BLV) && (Counter++ < 10000));
}

void
SetBestPath(PSPtr, Reversed)
	PathStruct	*PSPtr;
	int		Reversed;
{
	BestLPath = *PSPtr;
	if (Reversed)
		ReversePath(&BestLPath);
	BestLPathSet = 1;
}

void
CheckBestLP(PSPtr, Reversed)
	PathStruct	*PSPtr;
	int		Reversed;
{
	if (!BestLPathSet || (PSPtr->PathTotal > BestLPath.PathTotal))
		SetBestPath(PSPtr, Reversed);
}

/****************************************************************\
 *	Loop through maximizing functions until no improvement	*
\****************************************************************/
void
BTMassage(PSPtr, Reversed)
	PathStruct	*PSPtr;
	int		Reversed;
{
	long		Last;

	do {
		Last = PSPtr->PathTotal;
		MassageSL(PSPtr, 0);
		MassageSP(PSPtr);
		CalcWeightOfPath(PSPtr);
		CheckBestLP(PSPtr, Reversed);
		checktime();
	} while (PSPtr->PathTotal > Last);
}

void
LongestPath(PArrayPtr, PArrayQty, PArrayAlloced, StartRow, StartCol,
EndRow, EndCol, Reversed)
	PathStruct	**PArrayPtr;
	int		*PArrayQty;
	int		PArrayAlloced;
	unsigned char	StartRow, StartCol, EndRow, EndCol;
	int		Reversed;
{
	PathStruct	*PSPtr;
	
	PSPtr = GetNewPathPtr(PArrayPtr, PArrayQty, PArrayAlloced);
	PArrayQty--;
	AddToPath(PSPtr, StartRow, StartCol);
	TourInfo.UsedArray[StartRow][StartCol] = 1;
	if (PointTest(PSPtr, TourInfo.Limit - SPArrayPtr->RCQty + 1, EndRow,
EndCol)) {
		RestoreUsedAndWeight();
		SetUsedArrayLoop(PSPtr, 1, PSPtr->RCQty-2, 1);
		CalcWeightOfPath(PSPtr);
		BTMassage(PSPtr, Reversed);
		PArrayQty++;
	}
	checktime();
	RestoreUsedAndWeight();
}

/****************************************************************\
 * Generate long paths by by varying values used in determining	*
 * next direction. Generate backward paths in case the better	*
 * points are weighted toward the end. Originally had a		*
 * function that tried to merge the two, but no better result	*
 * was yielded from the test data, so I decided against		*
 * including it							*
\****************************************************************/
void
LongestPaths()
{
	for (CurrentRange = 5; CurrentRange < MaxRange; CurrentRange++)
		for (OffsetAdj = 0; OffsetAdj < 2; OffsetAdj++) {
			LongestPath(&LPArrayPtr, &LPArrayQty, &LPArrayAlloced,
SPArrayPtr->RCArray[SPArrayPtr->RCQty-1].Row,
				 SPArrayPtr->RCArray[SPArrayPtr->RCQty-1].Col,
SPArrayPtr->RCArray[0].Row, SPArrayPtr->RCArray[0].Col, 0);
			LongestPath(&BPArrayPtr, &BPArrayQty, &BPArrayAlloced,
SPArrayPtr->RCArray[0].Row, SPArrayPtr->RCArray[0].Col, 
				SPArrayPtr->RCArray[SPArrayPtr->RCQty-1].Row,
SPArrayPtr->RCArray[SPArrayPtr->RCQty-1].Col, 1);
		}
}


/****************************************************************\
 * Acres of tree stuff						*
\****************************************************************/
typedef struct {
	unsigned char	Row;
	unsigned char	Col;
	long		POff;
	long		PathAlt;
	long		Chil[8];
	int		ChilQty;
} TreeStruct;

TreeStruct	*CTreePtr = NULL;
long		CTreeQty = 0;
long		CTreeAlloced = 0;

int
GetNewTreePtr()
{
	if (CTreeQty + 1 > CTreeAlloced) {
		CTreeAlloced += 1000;
		if (CTreePtr)
			CTreePtr = (TreeStruct *) realloc(CTreePtr,
							CTreeAlloced * sizeof(TreeStruct));
		else
			CTreePtr = (TreeStruct *) malloc(CTreeAlloced * sizeof(TreeStruct));
	}
	memset(CTreePtr+CTreeQty, 0, sizeof(TreeStruct));
	CTreeQty++;
	return(1);
}

long
AllocateNewChild()
{
	GetNewTreePtr();
	return(CTreeQty-1);
}

void
AddChildToOffset(Offset, Row, Col)
	long		Offset;
	unsigned char	Row, Col;
{
	long	N;
	
	N = AllocateNewChild();
	CTreePtr[Offset].Chil[CTreePtr[Offset].ChilQty] = N;
	CTreePtr[N].Row = Row;
	CTreePtr[N].Col = Col;
	CTreePtr[N].POff = Offset;
	CTreePtr[N].PathAlt = CTreePtr[Offset].PathAlt +
			DeltaAlt(CTreePtr[Offset].Row, CTreePtr[Offset].Col,
CTreePtr[N].Row, CTreePtr[N].Col);
	CTreePtr[Offset].ChilQty++;
}

void
SetChilForOffset(Offset)
	long	Offset;
{
	int	Row, Col, I, J;
	
	for (I = -1; I <= 1; I++)
		for (J = -1; J <= 1; J++)
			if (I || J) {
				Row = CTreePtr[Offset].Row + I;
				Col = CTreePtr[Offset].Col + J;
				if (ValidRowColInt(Row, Col) &&
				    (TourInfo.UsedArray[(unsigned char)Row][(unsigned char)Col] !=
1)) {
					if (Distance(Row, Col, (int)CToRow, (int)CToCol) < 
						Distance((int)CTreePtr[Offset].Row, (int)CTreePtr[Offset].Col,
(int)CToRow, (int)CToCol))
						AddChildToOffset(Offset, (unsigned char)Row, (unsigned char)Col);
				}
			}
}



void
SetOPRec(Offset)
	long	Offset;
{
	if (Offset != 0)
		SetOPRec(CTreePtr[Offset].POff);
	AddToPath(&COPath, CTreePtr[Offset].Row, CTreePtr[Offset].Col);
}

void
RemoveDuplicates(Start, CTreeQty)
	long	Start, CTreeQty;
{
	long	I, J;
	
	for (I = Start; I < CTreeQty-1; I++) {
		if (CTreePtr[I].ChilQty != -1) 
			for (J = I+1; J < CTreeQty; J++)
				if ((CTreePtr[I].Row == CTreePtr[J].Row) &&
				    (CTreePtr[I].Col == CTreePtr[J].Col)) {
					if (CurrentMinimize ^ (CTreePtr[I].PathAlt >= CTreePtr[J].PathAlt))
						CTreePtr[J].ChilQty = -1;
					else {
						CTreePtr[I].ChilQty = -1;
						continue;
					}
				 }
	}
		
}

/****************************************************************\
 * Originally had a recursive version, hence the name.		*
 * Basically, given two points of Distance N, there is an 	*
 * optimum path of length N. I find it by generating all valid	*
 * moves and putting them in a tree. I then check the tree and	*
 * eliminate all paths that occupy the same point but have a	*
 * worse value, Continue till you reach the end			*
\****************************************************************/
long
GeneratePathsNonRecursive(Distance)
	int	Distance;
{
	int	I;
	long	J, Start=0, PrevStart=0;
	
	for (I = 0; I < Distance; I++) {
		Start = PrevStart;
		PrevStart = CTreeQty;
		for (J = Start; J < PrevStart; J++) {
			if (CTreePtr[J].ChilQty != -1) 
				SetChilForOffset(J);
		}
		checktime();
		RemoveDuplicates(Start, CTreeQty);
		checktime();
	}
	for (J = CTreeQty-1; J > 0; J--)
		if ((CTreePtr[J].ChilQty != -1) &&
			(CTreePtr[J].Row == CToRow) && (CTreePtr[J].Col == CToCol))
			return(J);
	return(0);
}

	
/****************************************************************\
 * generate the minimal length path from a point to a point.	*
\****************************************************************/
int
GetOptMin(Row, Col, ToRow, ToCol, Minimize)
	unsigned char	Row, Col, ToRow, ToCol;
	int		Minimize;
{
	long	Root;
	
	CTreeQty = 0;
	Root = AllocateNewChild();
	CTreePtr[Root].Row = Row;
	CTreePtr[Root].Col = Col;
	CurrentMinimize = Minimize;
	CToRow = ToRow;
	CToCol = ToCol;
	COLeaf = 0;
	memset(&COPath, 0, sizeof(PathStruct));
	if (COLeaf = GeneratePathsNonRecursive(Distance((int)Row, (int)Col,
(int)ToRow, (int)ToCol))) {
		COPath.RCQty = 0;
		SetOPRec(COLeaf);
		return(1);
	}
	return(0);
}

/****************************************************************\
 * Traverse a path for sub-paths whose distance is the same	*
 * as the number of points in the path. Given that path, 	*
 * replace it with one generated by  GetOptMin()		*
\****************************************************************/
int
MassageSL(PSPtr, Minimize)
	PathStruct	*PSPtr;
	int		Minimize;
{
	int	I, J, SO=0, TO, DistanceToStart;
	

	for (I = 1; I < PSPtr->RCQty; I++) {
		DistanceToStart = OffsetDistance(PSPtr, SO, I);
		if ( ((I - SO) > DistanceToStart) || (I == PSPtr->RCQty-1) ||
(DistanceToStart > 100)) {
			if (DistanceToStart > 1) {
				TO = I-1;
				if (!Minimize)
					SetUsedArrayLoop(PSPtr, SO+1, TO, 0);
				if (GetOptMin(PSPtr->RCArray[SO].Row, PSPtr->RCArray[SO].Col, 
					   PSPtr->RCArray[TO].Row, PSPtr->RCArray[TO].Col, Minimize) ) {
					for (J = 0; J < COPath.RCQty; J++) {
						PSPtr->RCArray[SO+J].Row = COPath.RCArray[J].Row;
						PSPtr->RCArray[SO+J].Col = COPath.RCArray[J].Col;
					}
				}
				if (!Minimize)
					SetUsedArrayLoop(PSPtr, SO, TO, 1);
			}
			SO = I-1;
		}
		else {
		}
	}
}

/****************************************************************\
 * Given a path, Add the best minimal length path to a point.	*
\****************************************************************/
int
AddMinimumPathToPath(PSPtr, Row, Col, ToRow, ToCol, Minimize)
	PathStruct	*PSPtr;
	unsigned char	Row, Col, ToRow, ToCol;
	int		Minimize;
{
	int	J;

	if (GetOptMin(Row, Col, ToRow, ToCol, Minimize)) {
		for (J = 1; J < COPath.RCQty; J++)
			AddToPath(PSPtr, COPath.RCArray[J].Row, COPath.RCArray[J].Col);
		return(1);
	}
	else
		return(0);
}

main(argc, argv)
	int	argc;
	char	*argv[];
{		
	if (argc > 1) {
		LoadFileInfo(argv[1], &TourInfo);
		CalcFileInfo();
		ShortestPath();
		InitUsedAndWeightFromPath(SPArrayPtr);
		LongestPaths();
		PrintAnswer(SPArrayPtr, &BestLPath);
	}
}





_________________________________________________________
DO YOU YAHOO!?
Get your free @yahoo.com address at http://mail.yahoo.com