maze.cpp.txt

MIT大学的Linux C语言编程,很好的资源!包括入门到进阶,最后到高级!

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <srgp.h> 

#define	DIM	50      /* size of the maze */
#define FSIZE	10000   /* Max size of the frontier set */
#define SCALE	10      /* size of a square on the screen */
#define PROB    0.66    /* Probability of leaving a square clear */
typedef enum {clear, visited, blocked} square_t;

typedef square_t maze_t[DIM][DIM];     /* Representation of the Maze */

typedef struct {
  int i, j;
} point_t;

typedef struct  {
  point_t cells[FSIZE];
  int size;
  int first;
} front_t;                             /* Representation of the frontier set */

void sleep(unsigned);

int IsEmpty(front_t * f)            /* Operations on the frontier set */
{
  return f->size == 0;
}

void MkEmpty(front_t *f)
{
  f->size=0;
  f->first=0;
}


point_t Next(front_t *f)
{
  point_t p;
 
  assert(f->size>0);
  p = f->cells[f->first];
  f->size--;
  f->first = f->first++ % FSIZE;
  return p;
}

/*
point_t Next(front_t *f)
{
  assert(f->size>0);
  return  f->cells[(f->first + f->size-- - 1) % FSIZE];
}
*/

void Add(front_t *f, point_t p) 
{
  assert(f->size<FSIZE);
  f->cells[(f->size++ + f->first) % FSIZE] = p;
}

/*
 * DrawSquare draws a square of the maze depending on its status s
 */

void DrawSquare(point_t p, square_t s, int scale)
{
  if (s == visited) {
    SRGP_setColor(2);
  } else if (s == blocked) {
    SRGP_setColor(1);
  } else {
    SRGP_setColor(0);
  }
  SRGP_fillRectangleCoord(p.i*scale, p.j*scale, (p.i + 1)*scale - 1, (p.j + 1)*scale - 1);
  SRGP_setColor(1);
  SRGP_rectangleCoord(p.i*scale, p.j*scale, (p.i + 1)*scale - 1, (p.j + 1)*scale - 1);
}

void DrawMaze(maze_t m, int scale)
{
  int i, j;
  point_t p;
  
  for (i = 0; i < DIM; ++i) {
    for (j = 0; j < DIM; ++j)  {
      p.i = i;
      p.j = j;
      DrawSquare(p, m[i][j], scale);
    }
  }
  SRGP_refresh();
}

void AddPair(maze_t m, front_t *f, int i, int j)
{
    point_t p;
    
    if (m[i][j]==clear) {
      m[i][j] = visited;
      p.i = i; p.j = j;
      DrawSquare(p, visited, SCALE);
      Add(f,p);
      DrawMaze(m,SCALE);
    } else return;
}

/*
 * Extend, extends the frontier by adding clear cells adjacent to the next
 * celll in the frontier and changing their status to visited.  
 * As a side effect Extend also marks the cells as visited on the display
 * of the maze. Assumes that the frontier is non empty.
 */

void Extend(maze_t m, front_t *f) 
{
  point_t curr;

  assert(!IsEmpty(f));

  curr = Next(f);
  AddPair(m,f,curr.i-1,curr.j);
  AddPair(m,f,curr.i,curr.j-1);
  AddPair(m,f,curr.i+1,curr.j);
  AddPair(m,f,curr.i,curr.j+1);
}

void Setup(maze_t maze, float prob) 
{
  int i, j;
	
  srand(time(NULL));
  prob = 1000.0*prob;

  /* the border */
  for (i = 0; i < DIM; ++i)  {
    maze[i][0] = blocked;
    maze[0][i] = blocked;
    maze[i][DIM-1] = blocked;
    maze[DIM-1][i] = blocked;
  }
  
  for (i = 1; i < DIM-1; ++i)  {
    for (j = 1; j < DIM-1; ++j)  {
      if (!(i==1&&j==1) && !(i==DIM-2&&j==DIM-2) && (rand()%1000)>prob)  {
	maze[i][j] = blocked;
      } else {
	maze[i][j] = clear;
      }
    }
  }
}

int main(void)
{
  maze_t maze;
  front_t frontier;
  point_t startp, endp;

  SRGP_begin("My Window", DIM*SCALE, DIM*SCALE, 0, FALSE);
  SRGP_loadCommonColor(2, "Orange");

  startp.i = 1; startp.j = 1;
  endp.i = DIM-2; endp.j = DIM-2;

  Setup(maze,PROB); 
  DrawMaze(maze,SCALE);

  getchar(); /* Wait for user to hit return */
  MkEmpty(&frontier);
  Add(&frontier, startp);
  
  while (!IsEmpty(&frontier) && maze[endp.i][endp.j] != visited) {
    Extend(maze, &frontier);
  }
  if (IsEmpty(&frontier)) {
    printf("Top right is NOT reachable.\n");
  } else { 
    printf("Top right is reachable.\n"); 
  }
  DrawMaze(maze,SCALE);
  getchar(); 

  SRGP_end();
  return EXIT_SUCCESS;
}