home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c072 / 1.ddi / PRG8_4.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-09-19  |  4.0 KB  |  142 lines
  1. /*Program 8_4 - The Maze Problem
  2.    by Stephen R. Davis, 1987
  3.  
  4.   Notice how small this reiterative solution to the maze problem
  5.   is.  The routine evaluate() checks the current location for
  6.   cheese (success) or wall (failure).  If the answer is neither,
  7.   it then calls itself in each of the 3 directions open to it
  8.   (we forbid it from looking in the direction from which it came)
  9.   until success or failure is attained.  The successful path is
  10.   marked with '.'s.
  11.  
  12.   Create mazes with any ASCII file editor.  Rules for mazes are:
  13.   - no loops
  14.   - halls marked with spaces
  15.   - cheese marked with '&' (need not be present)
  16.   - halls must be single space wide
  17.   - must have a single opening at the top; search starts here
  18. */
  19.  
  20. #include <stdio.h>
  21. #include <dos.h>
  22. /*use 0xb0000000 for monochrome and Hercules screens*/
  23. #define screenaddr ((unsigned far *)0xb8000000L)
  24. #define screen(y,x) screenaddr [(y * 80) + x]
  25.  
  26. #define space ' '
  27. #define cheese '&'
  28. #define path '.'
  29. #define VISIBLE 1
  30.  
  31. /*define prototypes for routines used*/
  32.  
  33. int main (int, char **);
  34. void readmaze (FILE *);
  35. int evaluate (unsigned, unsigned, unsigned);
  36. int value (unsigned, unsigned);
  37. void clrscrn (void);
  38.  
  39. /*Main - if one argument provided, read it up onto the screen and
  40.      evaluate it for a maze solution*/
  41. main (argc, argv)
  42.     int argc;
  43.     char *argv[];
  44. {
  45.     FILE *fp;
  46.     unsigned x;
  47.  
  48.     /*clear the screen - first line of maze must be at top of screen*/
  49.     clrscrn ();
  50.  
  51.     if (argc == 2) {
  52.          if (fp = fopen(argv[1], "r")) {
  53.               readmaze (fp);
  54.  
  55.               /*solve maze by finding a space in the top and
  56.                 searching from there*/
  57.               for (x = 0; (char)screen (0, x) != space; x++);
  58.               if (evaluate (0, x, 2))
  59.                    printf ("solution!\n");
  60.               else
  61.                    printf ("no solution found\n");
  62.          } else
  63.               printf ("File not found\n");
  64.     } else
  65.          printf ("Enter 'Prg8_4 <filename>'\n"
  66.                  "  where filename contains the maze to be solved\n");
  67. }
  68.  
  69. /*Readmaze - read a maze from a file onto the screen.  Transfer
  70.          only the character part to the screen.*/
  71. void readmaze (fptr)
  72.     FILE *fptr;
  73. {
  74.      char buffer [81];
  75.  
  76.      while (fgets (buffer, 80, fptr))
  77.           printf (buffer);
  78. }
  79.  
  80. /*Evaluate - solve the maze*/
  81.  
  82. int deltax [] = {0, 1, 0, -1};         /*define the directions*/
  83. int deltay [] = {-1, 0, 1, 0};
  84. int noallow [] = {2, 3, 0, 1};
  85.  
  86. int evaluate(yloc, xloc, prevmove)
  87.     unsigned yloc, xloc, prevmove;
  88. {
  89.     int i, val;
  90.     int value();
  91.  
  92.     if ((val = value(xloc, yloc)) == -1)   /*wall*/
  93.          return 0;
  94.     if (val == 1)                           /*cheese!*/
  95.          return 1;
  96.  
  97.     for (i = 0; i < 4; i++)                 /*4 possible moves*/
  98.          if (i != noallow[prevmove])        /*don't go backwards*/
  99.               if (evaluate(yloc+deltay[i], xloc+deltax[i], i)) {
  100.                    (char)screen (yloc, xloc) = path; /*found it!*/
  101.                    return 1;
  102.               }
  103.     return 0;                /*nothing down this path*/
  104. }
  105.  
  106. /*Value - evaluate the current location*/
  107. int value (xloc, yloc)
  108.     unsigned xloc, yloc;
  109. {
  110.     char curr;
  111.     int i;
  112.  
  113.     curr = (char)screen (yloc, xloc);
  114. #if VISIBLE                             /*make the search visible*/
  115.     (char)screen (yloc, xloc) = '#';
  116.     for (i = 0; i < 10000; i++) ;
  117.     (char)screen (yloc, xloc) = curr;
  118. #endif
  119.     switch (curr) {
  120.          case cheese: return  1;       /*cheese -> success*/
  121.          case space : return  0;       /*space -> keep looking*/
  122.          default    : return -1;       /*else -> can't go that way*/
  123.     }
  124. }
  125.  
  126. /*Clrscrn - clear the screen*/
  127. struct REGS regs;
  128. void clrscrn (void)
  129. {
  130.      regs.h.ah = 6;
  131.      regs.h.al = 0;
  132.      regs.h.bh = 7;
  133.      regs.x.cx = 0;
  134.      regs.x.dx = 0x1950;
  135.      int86 (0x10, ®s, ®s);
  136.  
  137.      regs.h.ah = 2;
  138.      regs.h.bh = 0;
  139.      regs.x.dx = 0;
  140.      int86 (0x10, ®s, ®s);
  141. }
  142.