home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / compiler / miracl / maze.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-01-13  |  2.4 KB  |  98 lines
  1. /*    Maze solver
  2.  
  3. Solve maze by finding shortest path in graph. Starting from node A, marked
  4. by 1, each node adjacent to n which has not already been marked with a lower
  5. value is marked with n+1; this process finishes when all paths to B have been
  6. tried and the shortest found. Trace unique path back from B to A.
  7. */
  8.  
  9. #include <stdio.h>
  10. #include <string.h>
  11. #include <system.h>
  12.  
  13. int sx=-1, sy,        /* start  A */
  14.     ex=-1, ey=-1,    /* finish B */
  15.     xs=0,  ys=0,    /* size of maze */
  16.     fd=1000;
  17.  
  18. char *maze[100], *work[100];
  19.  
  20. main()
  21. {
  22.    int x=0, y;
  23.    char in[100];
  24.  
  25.    while(*(work[ys]=strcpy(malloc(xs+1),
  26.       maze[ys]=strcpy(malloc(xs?((*in>0)&&(xs!=strlen(in))?
  27.      (exit(0),0):xs)+1:(xs=strlen(in))+1),gets(in)))))
  28.         ys++;
  29.  
  30.    for(x=y=0; y<ys; x=0, y++)
  31.       while(work[y][x])
  32.      switch(work[y][x++])
  33.         {
  34.         case 'A':  if(sx!=-1)
  35.               printf("more than one start"),
  36.               exit(0);
  37.  
  38.                sx=x-1; sy=y; work[sy][sx]=1;  /* start 1 */
  39.                break;
  40.  
  41.         case 'B':  if(ex!=-1)
  42.               printf("more than one end"),
  43.               exit(0);
  44.  
  45.                ex=x-1; ey=y; work[ey][ex]=(char)255;  /* finish -1 */
  46.                break;
  47.  
  48.         case ' ':  work[y][x-1]=(char)254;    /* blanks -2 */
  49.                break;
  50.  
  51.         default :  work[y][x-1]=(char)253;    /* border -3 */
  52.                break;
  53.         }
  54.  
  55.    next(sx,sy,1);    /* find all accessible paths from start A */
  56.  
  57.    if(fd<1000)
  58.       {
  59.       back(ex,ey,fd);  /* trace path of length fd from B back to A */
  60.       for(y=0; y<ys; y++)
  61.      printf("%s\n",maze[y]);
  62.       }
  63.    else
  64.       printf("no solutions");
  65. }
  66.  
  67. next(int x, int y, int t)
  68. {
  69.    int xl, xr, xu, xd;
  70.  
  71.    work[y][x]=t++;
  72.  
  73.    xl=work[y][x-1]; xr=work[y][x+1];
  74.    xu=work[y-1][x]; xd=work[y+1][x];
  75.  
  76.    /* if next to B and no shorter paths, store path length in fd */
  77.  
  78.    if(!(xl+1)|!(xr+1)|!(xu+1)|!(xd+1)) fd=t<fd?t:fd;
  79.  
  80.    /* if next square unreached or by longer path, recurse */
  81.  
  82.    if(xl==-2 || xl>t)  next(x-1,y,t);
  83.    if(xr==-2 || xr>t)  next(x+1,y,t);
  84.    if(xu==-2 || xu>t)  next(x,y-1,t);
  85.    if(xd==-2 || xd>t)  next(x,y+1,t);
  86. }
  87.  
  88. back(int x, int y, int t)
  89. {
  90.    if(!(x==ex && y==ey)) maze[y][x]='+'; work[y][x]=252;
  91.    if(--t==1) return;
  92.  
  93.    if(work[y][x-1]==t) { back(x-1,y,t); return; }
  94.    if(work[y][x+1]==t) { back(x+1,y,t); return; }
  95.    if(work[y-1][x]==t) { back(x,y-1,t); return; }
  96.    if(work[y+1][x]==t) { back(x,y+1,t); return; }
  97. }
  98.