home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 1 / HamRadio.cdr / tech / pcbsrcs2 / solve.c < prev    next >
C/C++ Source or Header  |  1991-02-07  |  15KB  |  457 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <fcntl.h>
  4. #include <io.h>
  5. #include "cell.h"
  6.  
  7. /*
  8. ** visit neighboring cells like this (where [9] is on the other side):
  9. **
  10. **    +---+---+---+
  11. **    | 1 | 2 | 3 |
  12. **    +---+---+---+
  13. **    | 4 |[9]| 5 |
  14. **    +---+---+---+
  15. **    | 6 | 7 | 8 |
  16. **    +---+---+---+
  17. */
  18.  
  19. static int delta[8][2] = { /* for visiting neighbors on the same side */
  20.      {  1, -1 }, /* northwest    */
  21.      {  1,  0 }, /* north        */
  22.      {  1,  1 }, /* northeast    */
  23.      {  0, -1 }, /* west        */
  24.      {  0,  1 }, /* east        */
  25.      { -1, -1 }, /* southwest    */
  26.      { -1,  0 }, /* south        */
  27.      { -1,  1 }  /* southeast    */
  28.     };
  29.  
  30. static int ndir[8] = { /* for building paths back to source */
  31.      FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
  32.      FROM_EAST,                  FROM_WEST,
  33.      FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
  34.     };
  35.  
  36. /* blocking masks for neighboring cells */
  37. #define BLOCK_NORTHEAST        ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
  38.                 | ANGLE_NEtoSE | ANGLE_NWtoNE \
  39.                 | SHARP_NtoNE | SHARP_EtoNE | HOLE )
  40. #define BLOCK_SOUTHEAST        ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
  41.                 | ANGLE_NEtoSE | ANGLE_SEtoSW \
  42.                 | SHARP_EtoSE | SHARP_StoSE | HOLE )
  43. #define BLOCK_SOUTHWEST        ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
  44.                 | ANGLE_SEtoSW | ANGLE_SWtoNW \
  45.                 | SHARP_StoSW | SHARP_WtoSW | HOLE )
  46. #define BLOCK_NORTHWEST        ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
  47.                 | ANGLE_SWtoNW | ANGLE_NWtoNE \
  48.                 | SHARP_WtoNW | SHARP_NtoNW | HOLE )
  49. #define BLOCK_NORTH        ( LINE_VERTICAL | BENT_NtoSE | BENT_NtoSW \
  50.                 | BENT_EtoNW | BENT_WtoNE \
  51.                 | BENT_StoNE | BENT_StoNW \
  52.                 | CORNER_NORTHEAST | CORNER_NORTHWEST \
  53.                 | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_NWtoNE \
  54.                 | DIAG_NEtoSW | DIAG_SEtoNW \
  55.                 | SHARP_NtoNE | SHARP_NtoNW \
  56.                 | SHARP_EtoNE | SHARP_WtoNW | HOLE )
  57. #define BLOCK_EAST        ( LINE_HORIZONTAL | BENT_EtoSW | BENT_EtoNW \
  58.                 | BENT_NtoSE | BENT_StoNE \
  59.                 | BENT_WtoNE | BENT_WtoSE \
  60.                 | CORNER_NORTHEAST | CORNER_SOUTHEAST \
  61.                 | ANGLE_NEtoSE | ANGLE_SEtoSW | ANGLE_NWtoNE \
  62.                 | DIAG_NEtoSW | DIAG_SEtoNW \
  63.                 | SHARP_EtoNE | SHARP_EtoSE \
  64.                 | SHARP_NtoNE | SHARP_StoSE | HOLE )
  65. #define BLOCK_SOUTH        ( LINE_VERTICAL | BENT_StoNE | BENT_StoNW \
  66.                 | BENT_EtoSW | BENT_WtoSE \
  67.                 | BENT_NtoSE | BENT_NtoSW \
  68.                 | CORNER_SOUTHEAST | CORNER_SOUTHWEST \
  69.                 | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_SEtoSW \
  70.                 | DIAG_NEtoSW | DIAG_SEtoNW \
  71.                 | SHARP_StoSE | SHARP_StoSW \
  72.                 | SHARP_EtoSE | SHARP_WtoSW | HOLE )
  73. #define BLOCK_WEST        ( LINE_HORIZONTAL | BENT_WtoNE | BENT_WtoSE \
  74.                 | BENT_NtoSW | BENT_StoNW \
  75.                 | BENT_EtoSW | BENT_EtoNW \
  76.                 | CORNER_SOUTHWEST | CORNER_NORTHWEST \
  77.                 | ANGLE_SWtoNW | ANGLE_SEtoSW | ANGLE_NWtoNE \
  78.                 | DIAG_NEtoSW | DIAG_SEtoNW \
  79.                 | SHARP_WtoSW | SHARP_WtoNW \
  80.                 | SHARP_NtoNW | SHARP_StoSW | HOLE )
  81.  
  82. struct block {
  83.     int r1, c1;
  84.     long b1;
  85.     int r2, c2;
  86.     long b2;
  87.     };
  88.  
  89. static struct block blocking[8] = { /* blocking masks for diagonal traces */
  90.      {  0, -1, BLOCK_NORTHEAST,  1, 0, BLOCK_SOUTHWEST },
  91.      {  0,  0, 0, 0, 0, 0 },
  92.      {  1,  0, BLOCK_SOUTHEAST,  0, 1, BLOCK_NORTHWEST },
  93.      {  0,  0, 0, 0, 0, 0 },
  94.      {  0,  0, 0, 0, 0, 0 },
  95.      {  0, -1, BLOCK_SOUTHEAST, -1, 0, BLOCK_NORTHWEST },
  96.      {  0,  0, 0, 0, 0, 0 },
  97.      { -1,  0, BLOCK_NORTHEAST,  0, 1, BLOCK_SOUTHWEST }
  98.     };
  99.  
  100. static long blocking2[8] = { /* blocking masks for drilling vias */
  101.      BLOCK_SOUTHEAST, BLOCK_SOUTH, BLOCK_SOUTHWEST,
  102.      BLOCK_EAST,                   BLOCK_WEST,
  103.      BLOCK_NORTHEAST, BLOCK_NORTH, BLOCK_NORTHWEST
  104.     };
  105.  
  106. static int selfok[5][8] = { /* mask for self-blocking corner effects */
  107.      { 1, 1, 1, 1, 1, 1, 1, 1 },
  108.      { 0, 0, 0, 0, 1, 0, 1, 0 },
  109.      { 0, 0, 0, 1, 0, 0, 1, 0 },
  110.      { 0, 1, 0, 0, 1, 0, 0, 0 },
  111.      { 0, 1, 0, 1, 0, 0, 0, 0 }
  112.     };
  113.  
  114. /* mask for hole-related blocking effects */
  115. static struct {
  116.     long trace;
  117.     int present;
  118.     } selfok2[8] = {
  119.      { HOLE_NORTHWEST, 0 },
  120.      { HOLE_NORTH, 0 },
  121.      { HOLE_NORTHEAST, 0 },
  122.      { HOLE_WEST, 0 },
  123.      { HOLE_EAST, 0 },
  124.      { HOLE_SOUTHWEST, 0 },
  125.      { HOLE_SOUTH, 0 },
  126.      { HOLE_SOUTHEAST, 0 }
  127.     };
  128.  
  129. static long newmask[8] = { /* patterns to mask out in neighbor cells */
  130.     0, CORNER_NORTHWEST|CORNER_NORTHEAST, 0,
  131.     CORNER_NORTHWEST|CORNER_SOUTHWEST, CORNER_NORTHEAST|CORNER_SOUTHEAST,
  132.     0, CORNER_SOUTHWEST|CORNER_SOUTHEAST, 0
  133.     };
  134.  
  135. static char fmt[] =
  136.   "  open=%ld, closed=%ld, moved=%ld, max=%ld, %ld%% of board";
  137.  
  138. extern int Nrows, Ncols; /* board dimensions */
  139.  
  140. /* measures of progress */
  141. extern int Ntotal;
  142. int Ncurrent = 0;
  143.  
  144. /* search statistics */
  145. extern long OpenNodes; /* total number of nodes opened */
  146. extern long ClosNodes; /* total number of nodes closed */
  147. extern long MoveNodes; /* total number of nodes moved */
  148. extern long MaxNodes; /* maximum number of nodes opened at one time */
  149.  
  150. extern void GetWork( int *, int *, char far * far *, int *, int *,
  151.     char far * far * );
  152. extern void InitQueue( void );
  153. extern void GetQueue( int *, int *, int *, int *, int * );
  154. extern void SetQueue( int, int, int, int, int, int, int );
  155. extern void ReSetQueue( int, int, int, int, int, int, int );
  156. extern long GetCell( int, int, int );
  157. extern void SetCell( int, int, int, long );
  158. extern void OrCell( int, int, int, long );
  159. extern int GetDir( int, int, int );
  160. extern void SetDir( int, int, int, int );
  161. extern int GetDist( int, int, int );
  162. extern void SetDist( int, int, int, int );
  163. extern int GetApxDist( int, int, int, int );
  164. extern int CalcDist( int, int, int );
  165.  
  166. void Solve( void );
  167. void Retrace( int, int, int, int, int );
  168.  
  169. void Solve () { /* route all traces */
  170.     int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
  171.     register int i;
  172.     char far *n1;
  173.     char far *n2;
  174.     long curcell, newcell, buddy, lastopen, lastclos, lastmove;
  175.     int newdist, olddir, success, self, echo;
  176.  
  177.     printf( "enter Solve()\n" );
  178.     echo = isatty( fileno(stdout) ) ? 1 : 0;
  179.     /* go until no more work to do */
  180.     for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
  181.             GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
  182.         Ncurrent++;
  183.         printf( "routing %Fs=%Fs, %d of %d\n", n1, n2, Ncurrent,
  184.             Ntotal );
  185.         if (r1 == r2 && c1 == c2) /* trivial case; already routed */
  186.             continue;
  187.         success = 0;
  188.         lastopen = lastclos = lastmove = 0;
  189.         InitQueue(); /* initialize the search queue */
  190.         a = GetApxDist( r1, c1, r2, c2 ); /* rough estimate */
  191.         SetQueue( r1, c1, TOP, 0, a, r2, c2 );
  192.         SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
  193.         /* search until success or we exhaust all possibilities */
  194.         for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
  195.             GetQueue( &r, &c, &s, &d, &a )) {
  196.             if (r == r2 && c == c2) { /* success! */
  197.                 Retrace( r1, c1, r2, c2, s ); /* lay traces */
  198.                 success++;
  199.                 break;
  200.                 }
  201.             /* report every 100 new nodes or so */
  202.             if (echo && (OpenNodes - lastopen > 100
  203.                 || ClosNodes - lastclos > 100
  204.                 || MoveNodes - lastmove > 100)) {
  205.                 lastopen = (OpenNodes/100)*100;
  206.                 lastclos = (ClosNodes/100)*100;
  207.                 lastmove = (MoveNodes/100)*100;
  208.                 printf( fmt, OpenNodes, ClosNodes,
  209.                     MoveNodes, MaxNodes,
  210.                     (ClosNodes*50)/(Nrows*Ncols) );
  211.                 putchar( '\r' );
  212.                 }
  213.             curcell = GetCell( r, c, s );
  214.             if (curcell&HOLE) {
  215.                 self = 5;
  216.                 /* set 'present' bits */
  217.                 for (i = 0; i < 8; i++)
  218.                     selfok2[i].present =
  219.                     ((curcell&selfok2[i].trace)?1:0);
  220.                 }
  221.             else if (curcell & CORNER_NORTHWEST)
  222.                 self = 1;
  223.             else if (curcell & CORNER_NORTHEAST)
  224.                 self = 2;
  225.             else if (curcell & CORNER_SOUTHWEST)
  226.                 self = 3;
  227.             else if (curcell & CORNER_SOUTHEAST)
  228.                 self = 4;
  229.             else
  230.                 self = 0;
  231.             for (i = 0; i < 8; i++) { /* consider neighbors */
  232.                 /* check self-block */
  233.                 if (self < 5 && !selfok[self][i])
  234.                     continue;
  235.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  236.                     || (nc = c+delta[i][1]) < 0
  237.                     || nc >= Ncols) /* off the edge? */
  238.                     continue;
  239.                 if (self == 5 && selfok2[i].present)
  240.                     continue;
  241.                 newcell = GetCell( nr, nc, s );
  242.                 /* check for non-target hole */
  243.                 if (newcell & HOLE) {
  244.                     if (nr != r2 || nc != c2)
  245.                         continue;
  246.                     }
  247.                 /* check for traces */
  248.                 else if (newcell & ~(newmask[i]))
  249.                     continue;
  250.                 /* check blocking on corner neighbors */
  251.                 if (delta[i][0] && delta[i][1]) {
  252.                     /* check first buddy */
  253.                     buddy = GetCell( r+blocking[i].r1,
  254.                         c+blocking[i].c1, s );
  255.                     if (buddy & (blocking[i].b1))
  256.                         continue;
  257.                     /* check second buddy */
  258.                     buddy = GetCell( r+blocking[i].r2,
  259.                         c+blocking[i].c2, s );
  260.                     if (buddy & (blocking[i].b2))
  261.                         continue;
  262.                     }
  263.                 olddir = GetDir( r, c, s );
  264.                 newdist = d+CalcDist( ndir[i], olddir,
  265.                     (olddir == FROM_OTHERSIDE)
  266.                     ? GetDir( r, c, 1-s ) : 0 );
  267.                 /* if (a) not visited yet, or (b) we have */
  268.                 /* found a better path, add it to queue */
  269.                 if (!GetDir( nr, nc, s )
  270.                     || (newdist < GetDist( nr, nc, s ))) {
  271.                     SetDir( nr, nc, s, ndir[i] );
  272.                     SetDist( nr, nc, s, newdist );
  273.                     SetQueue( nr, nc, s, newdist,
  274.                         GetApxDist( nr, nc, r2, c2 ),
  275.                         r2, c2 );
  276.                     }
  277.                 }
  278.             /* consider other side of board */
  279.             olddir = GetDir( r, c, s );
  280.             if (olddir == FROM_OTHERSIDE)
  281.                 continue; /* useless move, so don't bother */
  282.             if (curcell) /* can't drill via if anything here */
  283.                 continue;
  284.             /* check for holes or traces on other side */
  285.             if (newcell = GetCell( r, c, 1-s ))
  286.                 continue;
  287.             /* check for nearby holes or traces on both sides */
  288.             for (skip = i = 0; i < 8; i++) {
  289.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  290.                     || (nc = c+delta[i][1]) < 0
  291.                     || nc >= Ncols) /* off the edge? */
  292.                     continue;
  293.                 if (GetCell( nr, nc, s ) & blocking2[i]) {
  294.                     skip = 1; /* can't drill via here */
  295.                     break;
  296.                     }
  297.                 if (GetCell( nr, nc, 1-s ) & blocking2[i]) {
  298.                     skip = 1; /* can't drill via here */
  299.                     break;
  300.                     }
  301.                 }
  302.             if (skip) /* neighboring hole or trace? */
  303.                 continue; /* yes, can't drill via here */
  304.             newdist = d+CalcDist( FROM_OTHERSIDE, olddir, 0 );
  305.             /* if (a) not visited yet, or (b) we have found a
  306.             /* better path, add it to queue */
  307.             if (!GetDir( r, c, 1-s )
  308.                 || (newdist < GetDist( r, c, 1-s ))) {
  309.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  310.                 SetDist( r, c, 1-s, newdist );
  311.                 SetQueue( r, c, 1-s, newdist, a, r2, c2 );
  312.                 }
  313.             }
  314.         printf( fmt, OpenNodes, ClosNodes, MoveNodes, MaxNodes,
  315.             (ClosNodes*50)/(Nrows*Ncols) );
  316.         putchar( '\n' );
  317.         if (!success)
  318.             printf( "\t*!* UNSUCCESSFUL *!*\n" );
  319.         /* clear direction flags */
  320.         for (r = 0; r < Nrows; r++) {
  321.             for (c = 0; c < Ncols; c++) {
  322.                 SetDir( r, c, TOP, FROM_NOWHERE );
  323.                 SetDir( r, c, BOTTOM, FROM_NOWHERE );
  324.                 }
  325.             }
  326.         }
  327.     printf( "leave Solve()\n" );
  328.     }
  329.  
  330. static long bit[8][9] = { /* OT=Otherside */
  331.      /* N, NE, E, SE, S, SW, W, NW, OT */
  332. /* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE, 0,
  333.        SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW, (HOLE | HOLE_SOUTH) },
  334. /* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW, SHARP_StoSW,
  335.        0, SHARP_WtoSW, ANGLE_SWtoNW, (HOLE | HOLE_SOUTHWEST) },
  336. /* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
  337.        CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW, (HOLE | HOLE_WEST) },
  338. /* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW, BENT_StoNW,
  339.        ANGLE_SWtoNW, SHARP_WtoNW, 0, (HOLE | HOLE_NORTHWEST) },
  340. /* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE, LINE_VERTICAL,
  341.        BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW, (HOLE | HOLE_NORTH) },
  342. /* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE, DIAG_NEtoSW,
  343.        BENT_WtoNE, ANGLE_NWtoNE, (HOLE | HOLE_NORTHEAST) },
  344. /* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE, CORNER_SOUTHEAST,
  345.        BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW, (HOLE | HOLE_EAST) },
  346. /* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
  347.            ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW, (HOLE | HOLE_SOUTHEAST) }
  348.     };
  349.  
  350. void Retrace ( rr1, cc1, rr2, cc2, s )
  351.     /* work from target back to source, actually laying the traces */
  352.     int rr1, cc1, rr2, cc2, s; /* start on side s */
  353.     {
  354.     int r0, c0, s0, r1, c1, s1, r2, c2, s2;
  355.     register int x, y;
  356.     long b;
  357.  
  358.     r1 = rr2;
  359.     c1 = cc2;
  360.     s1 = s;
  361.     r0 = c0 = s0 = ILLEGAL;
  362.     do {
  363.         /* find where we came from to get here */
  364.         switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
  365.         case FROM_NORTH:    r2++;        break;
  366.         case FROM_EAST:            c2++;    break;
  367.         case FROM_SOUTH:    r2--;        break;
  368.         case FROM_WEST:            c2--;    break;
  369.         case FROM_NORTHEAST:    r2++;    c2++;    break;
  370.         case FROM_SOUTHEAST:    r2--;    c2++;    break;
  371.         case FROM_SOUTHWEST:    r2--;    c2--;    break;
  372.         case FROM_NORTHWEST:    r2++;    c2--;    break;
  373.         case FROM_OTHERSIDE:    s2 = 1-s2;    break;
  374.         default:
  375.             fprintf( stderr, "internal error: no way back\n" );
  376.             exit( -1 );
  377.             break;
  378.             }
  379.         if (r0 != ILLEGAL)
  380.             y = GetDir( r0, c0, s0 );
  381.         /* see if target or hole */
  382.         if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
  383.             switch (x) {
  384.             case FROM_NORTH:
  385.                 OrCell( r1, c1, s1, HOLE_NORTH );    break;
  386.             case FROM_EAST:
  387.                 OrCell( r1, c1, s1, HOLE_EAST );    break;
  388.             case FROM_SOUTH:
  389.                 OrCell( r1, c1, s1, HOLE_SOUTH );    break;
  390.             case FROM_WEST:
  391.                 OrCell( r1, c1, s1, HOLE_WEST );    break;
  392.             case FROM_NORTHEAST:
  393.                 OrCell( r1, c1, s1, HOLE_NORTHEAST );    break;
  394.             case FROM_SOUTHEAST:
  395.                 OrCell( r1, c1, s1, HOLE_SOUTHEAST );    break;
  396.             case FROM_SOUTHWEST:
  397.                 OrCell( r1, c1, s1, HOLE_SOUTHWEST );    break;
  398.             case FROM_NORTHWEST:
  399.                 OrCell( r1, c1, s1, HOLE_NORTHWEST );    break;
  400.             case FROM_OTHERSIDE:
  401.             default:
  402.                 fprintf( stderr, "internal error\n" );
  403.                 exit( -1 );
  404.                 break;
  405.                 }
  406.             }
  407.         else {
  408.             if ((y == FROM_NORTH || y == FROM_NORTHEAST
  409.                 || y == FROM_EAST || y == FROM_SOUTHEAST
  410.                 || y == FROM_SOUTH || y == FROM_SOUTHWEST
  411.                 || y == FROM_WEST || y == FROM_NORTHWEST)
  412.                 && (x == FROM_NORTH || x == FROM_NORTHEAST
  413.                 || x == FROM_EAST || x == FROM_SOUTHEAST
  414.                 || x == FROM_SOUTH || x == FROM_SOUTHWEST
  415.                 || x == FROM_WEST || x == FROM_NORTHWEST
  416.                 || x == FROM_OTHERSIDE)
  417.                 && (b = bit[y-1][x-1])) {
  418.                 OrCell( r1, c1, s1, b );
  419.                 if (b & HOLE)
  420.                     OrCell( r2, c2, s2, HOLE );
  421.                 }
  422.             else {
  423.                 fprintf( stderr, "internal error\n" );
  424.                 exit( -1 );
  425.                 }
  426.             }
  427.         if (r2 == rr1 && c2 == cc1) { /* see if source */
  428.             switch (x) {
  429.             case FROM_NORTH:
  430.                 OrCell( r2, c2, s2, HOLE_SOUTH );    break;
  431.             case FROM_EAST:
  432.                 OrCell( r2, c2, s2, HOLE_WEST );    break;
  433.             case FROM_SOUTH:
  434.                 OrCell( r2, c2, s2, HOLE_NORTH );    break;
  435.             case FROM_WEST:
  436.                 OrCell( r2, c2, s2, HOLE_EAST );    break;
  437.             case FROM_NORTHEAST:
  438.                 OrCell( r2, c2, s2, HOLE_SOUTHWEST );    break;
  439.             case FROM_SOUTHEAST:
  440.                 OrCell( r2, c2, s2, HOLE_NORTHWEST );    break;
  441.             case FROM_SOUTHWEST:
  442.                 OrCell( r2, c2, s2, HOLE_NORTHEAST );    break;
  443.             case FROM_NORTHWEST:
  444.                 OrCell( r2, c2, s2, HOLE_SOUTHEAST );    break;
  445.             case FROM_OTHERSIDE:
  446.             default:
  447.                 fprintf( stderr, "internal error\n" );
  448.                 exit( -1 );
  449.                 break;
  450.                 }
  451.             }
  452.         /* move to next cell */
  453.         r0 = r1; c0 = c1; s0 = s1;
  454.         r1 = r2; c1 = c2; s1 = s2;
  455.         } while (!(r2 == rr1 && c2 == cc1));
  456.     }
  457.