/*
** printed circuit board autorouter, Copyright (C) Randy Nevin 1989.
**
** you may give this software to anyone, make as many copies as you
** like, and post it on public computer bulletin boards and file
** servers. you may not sell it or charge any fee for distribution
** (except for media and postage), remove this comment or the
** copyright notice from the code, or claim that you wrote this code
** or anything derived from it.
**
** the author's address is: Randy Nevin, 1731 211th PL NE, Redmond,
** WA 98053. this code is available directly from the author; just
** send a floppy and a self-addressed floppy mailer with sufficient
** postage. however, you should first attempt to get a copy of this
** software package from the Dr. Dobb's Journal BBS.
*/

/* the low-order bit indicates a hole */
#define HOLE		 0x00000001L /* a conducting hole */

/* traces radiating outward from a hole to a side or corner */
#define HOLE_NORTH	 0x00000002L /* upward             */
#define HOLE_NORTHEAST	 0x00000004L /* upward and right   */
#define HOLE_EAST	 0x00000008L /* to the right       */
#define HOLE_SOUTHEAST	 0x00000010L /* downward and right */
#define HOLE_SOUTH	 0x00000020L /* downward           */
#define HOLE_SOUTHWEST	 0x00000040L /* downward and left  */
#define HOLE_WEST	 0x00000080L /* to the left        */
#define HOLE_NORTHWEST	 0x00000100L /* upward and left    */

/* straight lines through the center */
#define LINE_HORIZONTAL	 0x00000002L /* left-to-right line */
#define LINE_VERTICAL	 0x00000004L /* top-to-bottom line */

/* lines cutting across a corner, connecting adjacent sides */
#define CORNER_NORTHEAST 0x00000008L /* upper right corner */
#define CORNER_SOUTHEAST 0x00000010L /* lower right corner */
#define CORNER_SOUTHWEST 0x00000020L /* lower left corner  */
#define CORNER_NORTHWEST 0x00000040L /* upper left corner  */

/* diagonal lines through the center */
#define DIAG_NEtoSW	 0x00000080L /* northeast to southwest */
#define DIAG_SEtoNW	 0x00000100L /* southeast to northwest */

/* 135 degree angle side-to-far-corner lines */
#define BENT_NtoSE	 0x00000200L /* north to southeast */
#define BENT_NtoSW	 0x00000400L /* north to southwest */
#define BENT_EtoSW	 0x00000800L /* east to southwest  */
#define BENT_EtoNW	 0x00001000L /* east to northwest  */
#define BENT_StoNW	 0x00002000L /* south to northwest */
#define BENT_StoNE	 0x00004000L /* south to northeast */
#define BENT_WtoNE	 0x00008000L /* west to northeast  */
#define BENT_WtoSE	 0x00010000L /* west to southeast  */

/* 90 degree corner-to-adjacent-corner lines */
#define ANGLE_NEtoSE	 0x00020000L /* northeast to southeast */
#define ANGLE_SEtoSW	 0x00040000L /* southeast to southwest */
#define ANGLE_SWtoNW	 0x00080000L /* southwest to northwest */
#define ANGLE_NWtoNE	 0x00100000L /* northwest to northeast */

/* 45 degree angle side-to-near-corner lines */
#define SHARP_NtoNE	 0x00200000L /* north to northeast */
#define SHARP_EtoNE	 0x00400000L /* east to northeast  */
#define SHARP_EtoSE	 0x00800000L /* east to southeast  */
#define SHARP_StoSE	 0x01000000L /* south to southeast */
#define SHARP_StoSW	 0x02000000L /* south to southwest */
#define SHARP_WtoSW	 0x04000000L /* west to southwest  */
#define SHARP_WtoNW	 0x08000000L /* west to northwest  */
#define SHARP_NtoNW	 0x10000000L /* north to northwest */

/* directions the cell can be reached from (point to previous cell) */
#define FROM_NORTH	1
#define FROM_NORTHEAST	2
#define FROM_EAST	3
#define FROM_SOUTHEAST	4
#define FROM_SOUTH	5
#define FROM_SOUTHWEST	6
#define FROM_WEST	7
#define FROM_NORTHWEST	8
#define FROM_OTHERSIDE	9

#define	TOP	0
#define BOTTOM	1
#define EMPTY	0
#define ILLEGAL	-1

/* visit neighboring cells in this order
** (where [9] is on the other side):
**
**	+---+---+---+
**	| 1 | 2 | 3 |
**	+---+---+---+
**	| 4 |[9]| 5 |
**	+---+---+---+
**	| 6 | 7 | 8 |
**	+---+---+---+
*/

static int delta[8][2] = { /* for visiting neighbors on the same side */
	 {  1, -1 }, /* northwest	*/
	 {  1,  0 }, /* north		*/
	 {  1,  1 }, /* northeast	*/
	 {  0, -1 }, /* west		*/
	 {  0,  1 }, /* east		*/
	 { -1, -1 }, /* southwest	*/
	 { -1,  0 }, /* south		*/
	 { -1,  1 }  /* southeast	*/
	};

static int ndir[8] = { /* for building paths back to source */
	 FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
	 FROM_EAST,                  FROM_WEST,
	 FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
	};

/* blocking masks for neighboring cells */
#define BLOCK_NORTHEAST	( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
			| ANGLE_NEtoSE | ANGLE_NWtoNE \
			| SHARP_NtoNE | SHARP_EtoNE )
#define BLOCK_SOUTHEAST	( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
			| ANGLE_NEtoSE | ANGLE_SEtoSW \
			| SHARP_EtoSE | SHARP_StoSE )
#define BLOCK_SOUTHWEST	( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
			| ANGLE_SEtoSW | ANGLE_SWtoNW \
			| SHARP_StoSW | SHARP_WtoSW )
#define BLOCK_NORTHWEST	( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
			| ANGLE_SWtoNW | ANGLE_NWtoNE \
			| SHARP_WtoNW | SHARP_NtoNW )

struct block {
	int r1, c1;  long b1, h1;
	int r2, c2;  long b2, h2;
	};

static struct block blocking[8] = { /* blocking masks */
	 {  0, -1, BLOCK_NORTHEAST, HOLE_NORTHEAST,
	    1,  0, BLOCK_SOUTHWEST, HOLE_SOUTHWEST },
	 {  0,  0, 0, 0, 0, 0, 0, 0 },
	 {  1,  0, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
	    0,  1, BLOCK_NORTHWEST, HOLE_NORTHWEST },
	 {  0,  0, 0, 0, 0, 0, 0, 0 },
	 {  0,  0, 0, 0, 0, 0, 0, 0 },
	 {  0, -1, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
	   -1,  0, BLOCK_NORTHWEST, HOLE_NORTHWEST },
	 {  0,  0, 0, 0, 0, 0, 0, 0 },
	 { -1,  0, BLOCK_NORTHEAST, HOLE_NORTHEAST,
	    0,  1, BLOCK_SOUTHWEST, HOLE_SOUTHWEST }
	};

static int selfok[5][8] = { /* mask for self-blocking corner effects */
	 { 1, 1, 1, 1, 1, 1, 1, 1 },
	 { 0, 0, 0, 0, 1, 0, 1, 0 },
	 { 0, 0, 0, 1, 0, 0, 1, 0 },
	 { 0, 1, 0, 0, 1, 0, 0, 0 },
	 { 0, 1, 0, 1, 0, 0, 0, 0 }
	};

static long newmask[5][8] = { /* patterns to mask in neighbor cells */
	 { 0, 0, 0, 0, 0, 0, 0, 0 },
	 { 0, 0, 0, 0, CORNER_NORTHEAST | CORNER_SOUTHEAST, 0,
	   CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
	 { 0, 0, 0, CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0,
	   CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
	 { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0, 0,
	   CORNER_NORTHEAST | CORNER_SOUTHEAST, 0, 0, 0 },
	 { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0,
	   CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0, 0, 0 }
	};

/* board dimensions */
extern int Nrows;
extern int Ncols;

void Solve () { /* route all traces */
	int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
	register int i;
	char far *n1;
	char far *n2;
	long curcell, newcell, buddy;
	int newdist, olddir, success, self;

	/* go until no more work to do */
	for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
			GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
		if (r1 == r2 && c1 == c2) /* already routed */
			continue;
		success = 0;
		InitQueue(); /* initialize the search queue */
		/* get rough estimate of trace distance */
		a = GetApxDist( r1, c1, r2, c2 );
		SetQueue( r1, c1, TOP, 0, a, r2, c2 );
		SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
		/* search until success or we exhaust all possibilities */
		for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
			GetQueue( &r, &c, &s, &d, &a )) {
			if (r == r2 && c == c2) { /* success! */
				/* lay traces */
				Retrace( r1, c1, r2, c2, s );
				success++;
				break;
				}
			curcell = GetCell( r, c, s );
			if (curcell & CORNER_NORTHWEST)
				self = 1;
			else if (curcell & CORNER_NORTHEAST)
				self = 2;
			else if (curcell & CORNER_SOUTHWEST)
				self = 3;
			else if (curcell & CORNER_SOUTHEAST)
				self = 4;
			else
				self = 0;
			/* consider neighbors */
			for (i = 0; i < 8; i++) {
				/* check self-block */
				if (!selfok[self][i])
					continue;
				if ((nr = r+delta[i][0]) < 0
					|| nr >= Nrows
					|| (nc = c+delta[i][1]) < 0
					|| nc >= Ncols)
					/* off the edge */
					continue;
				newcell = GetCell( nr, nc, s );
				/* check for non-target hole */
				if (newcell & HOLE) {
					if (nr != r2 || nc != c2)
						continue;
					}
				else {
					newcell &= ~(newmask[self][i]);
					/* check for traces */
					if (newcell)
						continue;
					}
				/* check blocking on corner neighbors */
				if (delta[i][0] && delta[i][1]) {
					/* check first buddy */
					buddy = GetCell( r+blocking[i].r1,
						c+blocking[i].c1, s );
					if (buddy & HOLE) {
						if (buddy & (blocking[i].h1))
							continue;
						}
					else if (buddy & (blocking[i].b1))
						continue;
					/* check second buddy */
					buddy = GetCell( r+blocking[i].r2,
						c+blocking[i].c2, s );
					if (buddy & HOLE) {
						if (buddy & (blocking[i].h2))
							continue;
						}
					else if (buddy & (blocking[i].b2))
						continue;
					}
				olddir = GetDir( r, c, s );
				newdist = d+CalcDist( ndir[i], olddir,
					(olddir == FROM_OTHERSIDE)
					? GetDir( r, c, 1-s ) : 0 );
				/* if not visited yet, add it to queue */
				if (!GetDir( nr, nc, s )) {
					SetDir( nr, nc, s, ndir[i] );
					SetDist( nr, nc, s, newdist );
					SetQueue( nr, nc, s, newdist,
						GetApxDist( nr, nc, r2, c2 ),
						r2, c2 );
					}
				/* we might have found a better path */
				else if (newdist < GetDist( nr, nc, s )) {
					SetDir( nr, nc, s, ndir[i] );
					SetDist( nr, nc, s, newdist );
					ReSetQueue( nr, nc, s, newdist,
						GetApxDist( nr, nc, r2, c2 ),
						r2, c2 );
					}
				}
			/* consider other side of board */
			/* check for holes or traces on other side */
			if (newcell = GetCell( r, c, 1-s ))
				continue;
			skip = 0;
			/* check for nearby holes */
			for (i = 0; i < 8; i++) {
				if ((nr = r+delta[i][0]) < 0
					|| nr >= Nrows
					|| (nc = c+delta[i][1]) < 0
					|| nc >= Ncols)
					/* off the edge */
					continue;
				if (GetCell( nr, nc, s ) & HOLE) {
					/* neighboring hole */
					skip = 1;
					break;
					}
				}
			if (skip) /* neighboring hole? */
				continue; /* yes, can't drill one here */
			olddir = GetDir( r, c, s );
			newdist = d+CalcDist( FROM_OTHERSIDE, olddir,
				(olddir == FROM_OTHERSIDE)
				? GetDir( r, c, 1-s ) : 0 );
			/* if not visited yet, add it to queue */
			if (!GetDir( r, c, 1-s )) {
				SetDir( r, c, 1-s, FROM_OTHERSIDE );
				SetDist( r, c, 1-s, newdist );
				SetQueue( r, c, 1-s, newdist,
					a, r2, c2 );
				}
			/* we might have found a better path */
			else if (newdist < GetDist( r, c, 1-s )) {
				SetDir( r, c, 1-s, FROM_OTHERSIDE );
				SetDist( r, c, 1-s, newdist );
				ReSetQueue( r, c, 1-s, newdist,
					a, r2, c2 );
				}
			}
		if (!success)
			printf( "\t*!* UNSUCCESSFUL *!*\n" );
		/* clear direction flags */
		for (r = 0; r < Nrows; r++) {
			for (c = 0; c < Ncols; c++) {
				SetDir( r, c, TOP, EMPTY );
				SetDir( r, c, BOTTOM, EMPTY );
				}
			}
		}
	}

/* this table drives the retracing phase */
static long bit[8][9] = { /* OT=Otherside */
	 /* N, NE, E, SE, S, SW, W, NW, OT */
/* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE,
	   0, SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW,
	   (HOLE | HOLE_SOUTH) },
/* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW,
	   SHARP_StoSW, 0, SHARP_WtoSW, ANGLE_SWtoNW,
	   (HOLE | HOLE_SOUTHWEST) },
/* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
	   CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW,
	   (HOLE | HOLE_WEST) },
/* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW,
	   BENT_StoNW, ANGLE_SWtoNW, SHARP_WtoNW, 0,
	   (HOLE | HOLE_NORTHWEST) },
/* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE,
	   LINE_VERTICAL, BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW,
	   (HOLE | HOLE_NORTH) },
/* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE,
	   DIAG_NEtoSW, BENT_WtoNE, ANGLE_NWtoNE,
	   (HOLE | HOLE_NORTHEAST) },
/* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE,
	   CORNER_SOUTHEAST, BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW,
	   (HOLE | HOLE_EAST) },
/* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
           ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW,
	   (HOLE | HOLE_SOUTHEAST) }
	};

void Retrace ( rr1, cc1, rr2, cc2, s )
	/* work from target back to source, laying down the trace */
	int rr1, cc1, rr2, cc2, s; /* start on side s */
	{
	int r0, c0, s0, r1, c1, s1, r2, c2, s2;
	register int x, y;
	long b;

	r1 = rr2;
	c1 = cc2;
	s1 = s;
	r0 = c0 = s0 = ILLEGAL;
	do {
		/* find where we came from to get here */
		switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
		case FROM_NORTH:	r2++;		break;
		case FROM_EAST:			c2++;	break;
		case FROM_SOUTH:	r2--;		break;
		case FROM_WEST:			c2--;	break;
		case FROM_NORTHEAST:	r2++;	c2++;	break;
		case FROM_SOUTHEAST:	r2--;	c2++;	break;
		case FROM_SOUTHWEST:	r2--;	c2--;	break;
		case FROM_NORTHWEST:	r2++;	c2--;	break;
		case FROM_OTHERSIDE:	s2 = 1-s2;	break;
		default:
			fprintf( stderr, "internal error\n" );
			exit( -1 );
			break;
			}
		if (r0 != ILLEGAL)
			y = GetDir( r0, c0, s0 );
		/* see if target or hole */
		if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
			switch (x) {
			case FROM_NORTH:
			  OrCell( r1, c1, s1, HOLE_NORTH );  break;
			case FROM_EAST:
			  OrCell( r1, c1, s1, HOLE_EAST );  break;
			case FROM_SOUTH:
			  OrCell( r1, c1, s1, HOLE_SOUTH );  break;
			case FROM_WEST:
			  OrCell( r1, c1, s1, HOLE_WEST );  break;
			case FROM_NORTHEAST:
			  OrCell( r1, c1, s1, HOLE_NORTHEAST );  break;
			case FROM_SOUTHEAST:
			  OrCell( r1, c1, s1, HOLE_SOUTHEAST );  break;
			case FROM_SOUTHWEST:
			  OrCell( r1, c1, s1, HOLE_SOUTHWEST );  break;
			case FROM_NORTHWEST:
			  OrCell( r1, c1, s1, HOLE_NORTHWEST );  break;
			case FROM_OTHERSIDE:
			default:
				fprintf( stderr, "internal error\n" );
				exit( -1 );
				break;
				}
			}
		else {
			if ((y == FROM_NORTH
				|| y == FROM_NORTHEAST
				|| y == FROM_EAST
				|| y == FROM_SOUTHEAST
				|| y == FROM_SOUTH
				|| y == FROM_SOUTHWEST
				|| y == FROM_WEST
				|| y == FROM_NORTHWEST)
				&& (x == FROM_NORTH
				|| x == FROM_NORTHEAST
				|| x == FROM_EAST
				|| x == FROM_SOUTHEAST
				|| x == FROM_SOUTH
				|| x == FROM_SOUTHWEST
				|| x == FROM_WEST
				|| x == FROM_NORTHWEST
				|| x == FROM_OTHERSIDE)
				&& (b = bit[y-1][x-1])) {
				OrCell( r1, c1, s1, b );
				if (b & HOLE)
					OrCell( r2, c2, s2, HOLE );
				}
			else {
				fprintf( stderr, "internal error\n" );
				exit( -1 );
				}
			}
		if (r2 == rr1 && c2 == cc1) { /* see if source */
			switch (x) {
			case FROM_NORTH:
			  OrCell( r2, c2, s2, HOLE_SOUTH );  break;
			case FROM_EAST:
			  OrCell( r2, c2, s2, HOLE_WEST );  break;
			case FROM_SOUTH:
			  OrCell( r2, c2, s2, HOLE_NORTH );  break;
			case FROM_WEST:
			  OrCell( r2, c2, s2, HOLE_EAST );  break;
			case FROM_NORTHEAST:
			  OrCell( r2, c2, s2, HOLE_SOUTHWEST );  break;
			case FROM_SOUTHEAST:
			  OrCell( r2, c2, s2, HOLE_NORTHWEST );  break;
			case FROM_SOUTHWEST:
			  OrCell( r2, c2, s2, HOLE_NORTHEAST );  break;
			case FROM_NORTHWEST:
			  OrCell( r2, c2, s2, HOLE_SOUTHEAST );  break;
			case FROM_OTHERSIDE:
			default:
				fprintf( stderr, "internal error\n" );
				exit( -1 );
				break;
				}
			}
		/* move to next cell */
		r0 = r1; c0 = c1; s0 = s1;
		r1 = r2; c1 = c2; s1 = s2;
		} while (!(r2 == rr1 && c2 == cc1));
	}

int GetApxDist ( r1, c1, r2, c2 ) /* calculate approximate distance */
	int r1, c1, r2, c2;
	{
	register int d1, d2; /* row and column deltas */
	int d0; /* temporary variable for swapping d1 and d2 */

	/* NOTE: the -25 used below is because we are not going */
	/* from the center of (r1,c1) to the center of (r2,c2), */
	/* we are going from the edge of a hole at (r1,c1) to   */
	/* the edge of a hole at (r2,c2). holes are 25 mils in  */
	/* diameter (12.5 mils in radius), so we back off by 2  */
	/* radii.                                               */
	if ((d1 = r1-r2) < 0) /* get absolute row delta */
		d1 = -d1;
	if ((d2 = c1-c2) < 0) /* get absolute column delta */
		d2 = -d2;
	if (!d1) /* in same row? */
		return( (d2*50)-25 ); /* 50 mils per cell */
	if (!d2) /* in same column? */
		return( (d1*50)-25 ); /* 50 mils per cell */
	if (d1 > d2) { /* get smaller into d1 */
		d0 = d1;
		d1 = d2;
		d2 = d0;
		}
	d2 -= d1; /* get non-diagonal part of approximate route */
	return( (d1*71)+(d2*50)-25 ); /* 71 mils diagonally per cell */
	}

/* distance to go through a cell */
static int dist[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
	 /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
/* N  */ { 50, 60, 35, 60, 99, 60, 35, 60,   12, 12 },
/* NE */ { 60, 71, 60, 71, 60, 99, 60, 71,   23, 23 },
/* E  */ { 35, 60, 50, 60, 35, 60, 99, 60,   12, 12 },
/* SE */ { 60, 71, 60, 71, 60, 71, 60, 99,   23, 23 },
/* S  */ { 99, 60, 35, 60, 50, 60, 35, 60,   12, 12 },
/* SW */ { 60, 99, 60, 71, 60, 71, 60, 71,   23, 23 },
/* W  */ { 35, 60, 99, 60, 35, 60, 50, 60,   12, 12 },
/* NW */ { 60, 71, 60, 99, 60, 71, 60, 71,   23, 23 },

/* OT */ { 12, 23, 12, 23, 12, 23, 12, 23,   99, 99 },
/* OR */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 99 }
	};

/* distance around (circular) segment of hole */
static int circ[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
	 /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
/* N  */ { 39, 29, 20, 10,  0, 10, 20, 29,   99, 0 },
/* NE */ { 29, 39, 29, 20, 10,  0, 10, 20,   99, 0 },
/* E  */ { 20, 29, 39, 29, 20, 10,  0, 10,   99, 0 },
/* SE */ { 10, 20, 29, 39, 29, 20, 10,  0,   99, 0 },
/* S  */ {  0, 10, 20, 29, 39, 29, 20, 10,   99, 0 },
/* SW */ { 10,  0, 10, 20, 29, 39, 29, 20,   99, 0 },
/* W  */ { 20, 10,  0, 10, 20, 29, 39, 29,   99, 0 },
/* NW */ { 29, 20, 10,  0, 10, 20, 29, 39,   99, 0 },

/* OT */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 0 },
/* OR */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 0 }
	};

/* penalty for routing holes and turns, scaled by sharpness of turn */
static int penalty[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
	 /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
/* N  */ {  0,  5, 10, 15, 20, 15, 10,  5,   50, 0 },
/* NE */ {  5,  0,  5, 10, 15, 20, 15, 10,   50, 0 },
/* E  */ { 10,  5,  0,  5, 10, 15, 20, 15,   50, 0 },
/* SE */ { 15, 10,  5,  0,  5, 10, 15, 20,   50, 0 },
/* S  */ { 20, 15, 10,  5,  0,  5, 10, 15,   50, 0 },
/* SW */ { 15, 20, 15, 10,  5,  0,  5, 10,   50, 0 },
/* W  */ { 10, 15, 20, 15, 10,  5,  0,  5,   50, 0 },
/* NW */ {  5, 10, 15, 20, 15, 10,  5,  0,   50, 0 },

/* OT */ { 50, 50, 50, 50, 50, 50, 50, 50,  100, 0 },
/* OR */ {  0,  0,  0,  0,  0,  0,  0,  0,    0, 0 }
	};

/*
** x is the direction to enter the cell of interest.
** y is the direction to exit the cell of interest.
** z is the direction to really exit the cell, if y=FROM_OTHERSIDE.
**
** return the distance of the trace through the cell of interest.
** the calculation is driven by the tables above.
*/

int CalcDist ( x, y, z )
	/* calculate distance of a trace through a cell */
	int x, y, z;
	{
	int adjust;

	adjust = 0; /* set if hole is encountered */
	if (x == EMPTY)
		x = 10;
	if (y == EMPTY)
		y = 10;
	else if (y == FROM_OTHERSIDE) {
		if (z == EMPTY)
			z = 10;
		adjust = circ[x-1][z-1] + penalty[x-1][z-1];
		}
	return( dist[x-1][y-1] + penalty[x-1][y-1] + adjust );
	}