主要是从新翻了翻书,看到了迷宫求解的问题,于是乎便写了一个出来
由于时间紧张,所以没有自己产生随机矩阵,而是自己添的矩阵,以后再改成随机矩阵产生迷宫地图

由于写c写习惯了,所以还是发c的代码了
有时间的画再改用win32

Copy code

/* 程序名称： 迷宫求解
* 所用编译器： Turboc 2.0
* 作者：Killua
* 学校：电子科技大学
* 专业班级：04级软件工程2班
* 版本：1.0
*/

/*----------------------头文件--------------------*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>
#include<alloc.h>
#include<dos.h>
#include<graphics.h>
/*------------------------------------------------*/

/* ----------定义程序中用到的常量-----------------*/
#define STACKMAX 100         /*栈元素的最大存储结构*/
#define BGI
#define size 30             /* 方块的边长 */
#define TRUE 1
#define FALSE 0
#define ROWS 10             /* 迷宫的行数 */
#define COLS 10             /* 迷宫的列数 */
#define EAST 1             /* 方向东 */
#define SOUTH 2             /* 方向南 */
#define WEST 3             /* 方向西 */
#define NORTH 4             /* 方向北 */

/*-------------------------------------------------*/

/*-------------------全局常量----------------------*/

  /* 迷宫中墙的数据 ，每两个一组
  * 比如第一组(3,1)表示在board[3][1]处有墙
  */
  int board_data[] = {3, 1, 3, 2, 7, 1, 7, 2,
                5, 3, 6, 3, 2 ,4, 3, 4,
                4, 4, 4, 5, 2, 6, 2, 7,
                3, 7, 4, 7, 1, 8, 6, 6,
                6, 7, 7, 7};

  char Board[COLS][ROWS];               /* 存储迷宫数据的矩阵 */
/*-------------------------------------------------*/



/*------------------定义一系列结构体---------------*/
typedef int Direction;                 /* mouse移动的方向 */

typedef struct Position                 /* mouse位置坐标的结构体 */
{
  int x;
  int y;
}Position;


/* 存入栈的元素的结构体 */
typedef struct elemType
{
  Position pos;             /* mouse的位置 */
  Direction direction;         /* 下一个移动的方向 */
}elemType;

typedef struct stack/*定义栈结构*/
{
elemType elem[STACKMAX];/*存储栈元素的数组*/
int top;/*栈顶元素的下标*/
}stack;

/*栈的初始化*/
void Init_stack(stack* s)
{
s->top = 0;
}

/*压入元素入栈*/
int push(stack* s,elemType x)
{
if( s->top == STACKMAX )
  return FALSE;
  else
    {
    s->top = s->top + 1;
    s->elem[s->top] = x;
    return TRUE;
    }
}

/*元素出栈*/
elemType pop(stack* s)
{
      s->top = s->top - 1;
      return s->elem[s->top+1];
}

/* 栈判空函数 */
int Stack_Empty(stack *s)
{
  if (s->top == 0)
    return TRUE;
    else
        return FALSE;
}
/*--------------------------------------------------------*/


/*-----------------------函数声明--------------------------*/
void Init_graph(void);                   /* 初始化为图形模式 */
void Draw_Border(void);                   /* 画迷宫的边框 */
void Draw_Text(void);                     /* 写文字 */
void Init_Board(void);                   /* 初始化迷宫数据 */
void Draw_Rect(int x, int y);               /* 画迷宫墙的方块 */
void Draw_Board(void);                   /* 画迷宫 */
void Init(void);                       /* 将所有的初始化包含其中 */
int Pass(Position curpos);                 /* 判断mouse能不能在当前位置通过*/
void FootPrint(Position curpos);             /* mouse走过的位置置1 */
Position NextPos(Position curpos, Direction direction); /* 取得mouse要走的下一个位置 */
void Draw_Mouse(int x, int y);                 /* 画mouse */
int MazePath(Position start, Position end);       /* 若迷宫中存在从入口到出口的的路径，就让栈存储次路径 */

/*---------------------------------------------------------*/


/*------------------------函数定义-----------------------------------------*/

/*-----------------进入图形模式函数Init_graph-------------*/
void Init_graph(void)
{
  int gdriver=DETECT,gmode;
  registerbgidriver(EGAVGA_driver);
  initgraph(&gdriver, &gmode, "c:\\turboc2");
}
/*--------------------------------------------------------*/

/*------------------画迷宫边框的函数--------------------------*/
void Draw_Border(void)
{
  int space = 5;
  setfillstyle(XHATCH_FILL, YELLOW);
  bar(290, 90-space-1, 590, 90-1);
  bar(290-space-1, 90-space-1, 290-1, 390+space+1);
  bar(590+1, 90-space-1, 590+space+1, 390+space+1);
  bar(290, 390+1, 590, 390+1+space);
}

/*-----------------------写文字-----------------------------*/
void Draw_Text(void)
{
  setcolor(GREEN);
  outtextxy(50, 120, "Program: MazePath");
  outtextxy(50, 140, "Version: 1.0");
  outtextxy(50, 160, "Author: Liu Chao");
  outtextxy(50, 180, "QQ: 53408770");
  outtextxy(50, 200, "Email: [email]kangtalc@163.com[/email]");
  outtextxy(50, 220, "Software School of UESTC");
}
/*----------------------------------------------------------*/

/*---------------------初始化迷宫的数据--------------------*/
void Init_Board(void)
{
  /* 如果迷宫(i, j)位置有墙，则置Board[i][j]为‘#’
  * 否则为0
  */
  int array_size;

  int i , j;

  for (i = 0; i < 10; i++)
    {
        for (j = 0; j < 10; j++)
        {
          if (i == 0 || j == 0 || i == 9 || j == 9)
            Board[i][j] = '#';
            else
                Board[i][j] = 0;
        }
    }
  array_size = sizeof(board_data)/sizeof(int);
  for (i = 0; i < array_size; i += 2)
    Board[board_data[i]][board_data[i+1]] = '#';
}
/*---------------------------------------------------------*/


/*----------------------画方块的函数----------------------*/
void Draw_Rect(int x, int y)
{
  int realx, realy;
  realx = x * size + 290;
  realy = y * size + 90;
  bar(realx + 1, realy + 1, realx + size - 1, realy + size - 1);
}
/*------------------------------------------------------------*/


/*-----------------------画迷宫障碍物的函数-------------------*/
void Draw_Board(void)
{

  int i, j;
  for (i = 0; i < COLS; i++)
    {
        for (j = 0; j < ROWS; j++)
        {
          if (Board[i][j] == '#')
          {
            setfillstyle(SOLID_FILL, LIGHTRED);
            Draw_Rect(i, j);
          }
        }
    }
}
/*-------------------------------------------------------------*/

/*---------------将上面的各个函数封装为一个函数做初始化--------*/
void Init(void)
{
  Init_graph();
  Init_Board();
  Draw_Border();
  Draw_Text();
  Draw_Board();
}
/*-------------------------------------------------------------*/

/*------------------判断mouse在当前位置能不能通过--------------*/
int Pass(Position curpos)
{

  if (Board[curpos.x][curpos.y] == 1 || Board[curpos.x][curpos.y] == '#')
    return FALSE;
    else
        return TRUE;
}
/*-------------------------------------------------------------*/

/*-----------------------记录mouse走过的痕迹------------------*/
void FootPrint(Position curpos)
{
  Board[curpos.x][curpos.y] = 1;
}
/*------------------------------------------------------------*/


/*----------------取得mouse可能移动到的下一个位置-------------*/
Position NextPos(Position curpos, Direction direction)
{
  switch(direction)
  {
    case EAST:
        curpos.x++;
        break;
    case SOUTH:
        curpos.y++;
        break;
    case WEST:
        curpos.x--;
        break;
    case NORTH:
        curpos.y--;
    }
    return curpos;
}
/*---------------------------------------------------------------*/

/*-----------------------画mouse---------------------------------*/
void Draw_Mouse(int x, int y)
{
  int realx, realy;
  realx = x * size + 290;
  realy = y * size + 90;
  bar(realx + 3, realy + 3, realx + size - 3, realy + size - 3);
}

/*----------------------------------------------------------------*/



/*---------------------------时间延迟函数-----------------------*/
void time_delay()
{
double i=0;
for(i=0;i<18390000;)
i++;
}
/*--------------------------------------------------------------*/


/*--------------------------求从START到END的一条路径------------*/

/* 若迷宫MAZE中存在从入口START到出口END的通道
* 则求得一条存放在栈中（从栈底到栈顶）
* 并返回TRUE，否则返回FALSE
*/
int MazePath(Position start, Position end)
{
  stack s;
  elemType e;

  Position curpos = start;       /* 设定当前位置为入口位置 */
  Position last_pos = curpos;     /* 记录上一个位置 */
  Init_stack(&s);             /* 初始化栈 */

  do
  {
    if (Pass(curpos))                       /* 如果 mouse能在当前位置通过，即是未曾走过的通道块*/
        {
          FootPrint(curpos);
         
          /* 清除上一个方块，画当前方块 */
          setfillstyle(SOLID_FILL, BLACK);
          Draw_Mouse(last_pos.x, last_pos.y);
          setfillstyle(SOLID_FILL, LIGHTBLUE);
          Draw_Mouse(curpos.x, curpos.y);
          time_delay();
      last_pos = curpos;/*将当前方块设为上一个方块*/
         
         
          /* 加入路径 */
          e.pos = curpos;
          e.direction = EAST;
          push(&s, e);/* 压入栈 */
         
         

          /* 如果到了出口 */
          if (curpos.x == end.x && curpos.y == end.y)
            {
                setfillstyle(SOLID_FILL, LIGHTBLUE);
            Draw_Mouse(curpos.x, curpos.y);
          return TRUE;
          }
            /*下一个位置是当前位置的东邻*/
            curpos = NextPos(curpos, EAST);
        }
        else   /* 不能在当前位置通过 */
          {
            if (!Stack_Empty(&s))
                {
                  {
                    /* 出栈，并且从画mouse */
                    e = pop(&s);
                    setfillstyle(SOLID_FILL, BLACK);
              Draw_Mouse(last_pos.x, last_pos.y);
              setfillstyle(SOLID_FILL, LIGHTBLUE);
              Draw_Mouse(e.pos.x, e.pos.y);
              time_delay();
          last_pos = e.pos;
          }
         
                    /* 找到一个可通的相邻块，并且从画mouse */
                    while ( e.direction == NORTH && !Stack_Empty(&s))
                    {
                        e = pop(&s);
                          setfillstyle(SOLID_FILL, BLACK);
              Draw_Mouse(last_pos.x, last_pos.y);
              setfillstyle(SOLID_FILL, LIGHTBLUE);
              Draw_Mouse(e.pos.x, e.pos.y);
              time_delay();
          last_pos = e.pos;
                    }
                    if (e.direction < NORTH)
                        {
                          e.direction++;                 /* 探索下一个方向 */
                          push(&s, e);                
                          curpos = NextPos(e.pos, e.direction); /* 设定当前位置为该新方向上的相邻块 */
                        }
                }
          }
  }while(!Stack_Empty(&s));
}



/* 主函数 */
int main()
{
  /* 设定能否找到路径 */
  int status = FALSE;
 
  /* 设定入口和出口 */
  Position start, end;
  start.x = 1, start.y = 1;
  end.x = 8, end.y = 8;
  Init();
 
  status = MazePath(start, end);


  if(status)
    {
        setcolor(BLUE);
      outtextxy(50, 300, "The mouse can find the Path!");
      getch();
    }
    else
        {
          setcolor(BLUE);
          outtextxy(50, 300, "The Path is wrong");
          getch();
        }
  closegraph();
  return 0;
}