迷宫算法

#include<stdio.h> #include <malloc.h> #include <stdlib.h> #include <string.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define RANGE 100 //迷宫大小 #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间增量 #define ROW 9 //迷宫的行数 #define COL 8 //迷宫的列数 typedef int Status; //函数的返回值 typedef int DirectiveType; //下一个通道方向 typedef struct{ int row; //行数 int col; //列数 }PosType; typedef struct{ int ord; //通道快在路径上的"序号" PosType seat; //通道快在迷宫中的" 坐标位置 " DirectiveType di; //往下一个通道坐标位置的" 方向 " }SElemType; //栈的元素类型 typedef struct{ SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize; //栈的大小 }SqStack; typedef struct{ int m,n; int arr[RANGE][RANGE]; //各个通道位置用二维数组表示 }MazeType; //迷宫类型 //构造一个空栈S Status InitStack(SqStack &s){ s.base = (SElemType * ) malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!s.base) exit(OVERFLOW); s.top=s.base; s.stacksize=STACK_INIT_SIZE; return OK; } //将元素e压入栈中 Status Push(SqStack &s, SElemType e){ if(s.top-s.base >= s.stacksize){ //栈满，追加存储空间 s.base = (SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!s.base) exit(OVERFLOW); s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; } *s.top++ = e; return OK; } //判断栈是否为空 Status StackEmpty(SqStack s) { return s.base == s.top; } //退栈操作 Status Pop(SqStack &s, SElemType &e){ if(s.top==s.base)return ERROR; e = * --s.top; return OK; } Status InitMaze(MazeType &maze, int a[][COL], int row, int col){ //将输入的row行和col列的二维数组(0/1) 设置为迷宫maze的初值，并加上一层围墙 for(int i=1;i<=row;i++){ for(int j=1;j<=col;j++){ maze.arr[i][j] = a[i-1][j-1]; //将数组的值赋给maze } } //加上围墙 for(int j=0;j<=col+1;j++){ maze.arr[0][j] = maze.arr[row+1][j]=1; } for(i=0;i<=row+1;i++){ maze.arr[i][0] = maze.arr[i][col+1]=1; } maze.m = row; maze.n = col; return OK; } Status Pass(MazeType maze,PosType curpos){ return maze.arr[curpos.row][curpos.col] == 0; } //判断当前节点是否通过，未曾走过的通道块 Status FootPrint(MazeType &maze,PosType curpos){ maze.arr[curpos.row][curpos.col]='*'; return OK; } //留下足迹 SElemType CreateSElem(int step, PosType pos, int di){ SElemType e; e.ord = step; e.seat = pos; e.di = di; return e; } //创建元素e Status PosEquare(PosType pos1, PosType pos2){ return pos1.row==pos2.row && pos1.col==pos2.col ; } //判断两结点是否相等，用于判断出口 void PrintMaze(MazeType maze,int row,int col){ //打印迷宫信息 int i,j; printf("迷宫的路径图为(用'*'表示,'#'表示障碍。):/n"); for(i=1;i<=row;i++){ for(j=1;j<=col;j++){ switch(maze.arr[i][j]) { case 0: printf(" "); break; case '*': //*表示可以通过的标记 printf("* "); break; case '@': //@表示不能通过的标记 printf("@ "); break; case 1: //表示迷宫中的障碍 printf("# "); break; } } printf("/n"); } printf("/n/n路径的坐标位置为:/n"); for(i=1;i<=row;i++) for(j=1;j<=col;j++) { if(maze.arr[i][j]=='*') printf("(%d,%d)—>",i,j); } } //返回当前节点的下一节点 PosType NextPos(PosType curpos, DirectiveType di){ PosType pos = curpos; switch(di) { case 1: pos.col++; break; //东 case 2: pos.row++; break; //南 case 3: pos.col--; break; //西 case 4: pos.row--; break; //北 } return pos; } //留下不能通过的标记 Status MarkPrint(MazeType &maze,PosType curpos){ maze.arr[curpos.row][curpos.col]='@'; return OK; } Status MazePath(MazeType &maze,PosType start, PosType end){ //若迷宫maze中存在从入口start到出口end的一条通道，则求得一条存放在栈中 //从栈底到栈顶），并返回TRUE，否则返回FALSE SqStack s; SElemType e; InitStack(s); //构造空栈，以后用来存储通道序号 PosType curpos = start; //设定" 当前位置 "为" 入口位置 " int curstep = 1; //探索第一步 do{ if( Pass(maze,curpos) ){ //如果当前位置可以通过,即是未曾走到的通道块 FootPrint(maze,curpos); //留下足迹 e = CreateSElem(curstep,curpos,1); //创建元素 Push(s,e); if( PosEquare(curpos,end) ) return TRUE; curpos =NextPos(curpos,1); //获得下一节点:当前位置的东邻 curstep++; //探索下一步 }else{ //当前位置不能通过 if(!StackEmpty(s)){ Pop(s,e); while(e.di==4 && !StackEmpty(s) ){ MarkPrint(maze,e.seat); Pop(s,e);curstep--; //留下不能通过的标记,并退回一步 } if(e.di<4){ e.di++; Push(s,e); //换一个方向探索 curpos = NextPos(e.seat,e.di); //求下一个节点 } } } }while(!StackEmpty(s)); return FALSE; } void main() { int a[ROW][COL]; printf("请输入迷宫的数据(0或1),0表示通道，1表示障碍，共%d行%d列:/n",ROW,COL); for(int i=0;i<ROW;i++) { for(int j=0; j<COL;j++) { scanf("%d",&a[i][j]); } } PosType start,end; start.row = 1;start.col=1; end.row = 9; end.col = 8; MazeType maze; InitMaze(maze,a,ROW,COL); if(MazePath(maze,start,end)) PrintMaze(maze,ROW,COL); else printf("没有找到通路!/n"); }