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