迷宫求解 [栈实现]

题目：

 这是栈的一个非常经典的应用；采用穷举法，用栈来记录走过的路线；如果发现前方的路走不通，就通过退栈来达到往回走的效果！！！
为了更加直观的展示，采用了 EasyX 的图形库绘制地图和求解的路线。

效果如下：

注释：左上角白色方块是起点；右下角白色方块是终点。

绘制地图代码测试：

 #include <graphics.h>   // 引用图形库头文件
 #include <conio.h>
int main( )
{
   initgraph(300, 300);  //初始化图形窗口
   setlinecolor(BLUE);

   for(i=0;i<10;i++){  //绘制地图
    for(j=0;j<10;j++){
      if(in[i][j]!=1)
        fillrectangle(j*30,i*30,j*30+30,i*30+30);
    }
   }
   _getch();              // 按任意键继续
   closegraph();          // 关闭绘图窗口
   return 0;
}

EasyX 好用一批！

下面是整体代码：

/************************
 *Stack application [迷宫求解]
 *SENCOM LAB
 *Michael Jiang
 *2018-9-20
 *2018-9-21
 ************************/
 #include "stdio.h"
 #include "stdlib.h"
 #include <graphics.h>   // 引用图形库头文件
 #include <conio.h>

 #define OK 1
 #define ERROR 0
 #define TRUE 1
 #define FALSE 0
 #define ElemType int //这里直接根据需求改数据类型
 #define STACK_INIT_SIZE 50
 #define STACKINCREMENT 5


 typedef struct {
   ElemType *base;
   ElemType *top;
   int stacksize;
 }SqStack;

typedef struct {
  int x;
  int y;
}Point;

 //active funtion
 int InitStack(SqStack &s)
 {
   s.base = (ElemType *)malloc(sizeof(ElemType)*STACK_INIT_SIZE);
   if(!s.base) return ERROR;
   s.top = s.base;
   s.stacksize = STACK_INIT_SIZE;
   return OK;
 }
 int DestroyStack(SqStack &s)
 {
   free(s.base);
   return OK;
 }
 int ClearStack(SqStack &s)
 {
   s.top = s.base;
   return OK;
 }
 ElemType GetTop(SqStack &s)
 {
   ElemType e;
   if(s.top == s.base) return ERROR;
   e = *(s.top-1);
   return e;
 }
 int Push(SqStack &s,ElemType e)
 {
   if(s.top - s.base >= s.stacksize) {
   s.base = (ElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(ElemType));
   if(!s.base)exit(-1);
   s.top = s.base + s.stacksize;
   s.stacksize += STACKINCREMENT;
   }
   *s.top = e;
   s.top++;
   return OK;
 }
 int Pop(SqStack &s)
 {
   if(s.top == s.base) return ERROR;
   s.top--;
   return OK;
 }

 //Static funtion
 int StackEmpty(SqStack s)
 {
   if(s.top == s.base)
     return TRUE;
   else
     return FALSE;
 }
 int StackTravel(SqStack s)
 {
   ElemType *p = s.top;
   printf("top->");
   for(p--;p >= s.base ; p--){
     printf("%d->",*p);
   }
   printf("base\n");
   return OK;
 }

char turn(int in[][10],Point p) //转向函数
{
  if(in[p.x+1][p.y] == 0)
    return 'd';  //向下
  else if(in[p.x][p.y-1] == 0)
    return 'l';  //向左
  else if(in[p.x][p.y+1] == 0)
    return 'r';  //向右
  else if(in[p.x-1][p.y] == 0)
    return 'u';  //向上
  else return 'x'; //死路
}

 //main funtion
 int main(int argc, char const *argv[]) {
   /* code */
   int i,j;
   int in[10][10] = {  //in[][]存放地图数据
     {1,1,1,1,1,1,1,1,1,1},
     {1,2,0,1,0,0,0,1,0,1},
     {1,0,0,1,0,0,0,1,0,1},
     {1,0,0,0,0,1,1,0,0,1},
     {1,0,1,1,1,0,0,0,0,1},
     {1,0,0,0,1,0,0,0,0,1},
     {1,0,1,0,0,0,1,0,0,1},
     {1,0,1,1,1,0,1,1,0,1},
     {1,1,0,0,0,0,0,0,1,1},
     {1,1,1,1,1,1,1,1,1,1}
   };
   SqStack s;
   if(!InitStack(s))exit(-1);
   Point p;
   p.x = 1; //初始化起点
   p.y = 1;
   Push(s,p.x);Push(s,p.y);
   initgraph(300, 300);  //初始化图形窗口
   setlinecolor(BLUE);

   for(i=0;i<10;i++){  //绘制地图
    for(j=0;j<10;j++){
      if(in[i][j]!=1)
        fillrectangle(j*30,i*30,j*30+30,i*30+30);
    }
   }
   while((p.x != 8) || (p.y != 8)){
     switch(turn(in,p)){
       case 'u' : in[p.x][p.y]=2;p.x-=1;Push(s,p.x);Push(s,p.y);break;//先在当前位置写如2表示走过然后走向下一个并推入栈
       case 'd' : in[p.x][p.y]=2;p.x+=1;Push(s,p.x);Push(s,p.y);break;
       case 'l' : in[p.x][p.y]=2;p.y-=1;Push(s,p.x);Push(s,p.y);break;
       case 'r' : in[p.x][p.y]=2;p.y+=1;Push(s,p.x);Push(s,p.y);break;
       case 'x' : in[p.x][p.y]=1;Pop(s);Pop(s);p.y=*(s.top-1);p.x=*(s.top-2);break;
     }
     if(p.x == 1 && p.y == 1) {  //没有解时会退回原点
       printf("NO WAY!\n");
       break;
     }
   }
   setfillcolor(GREEN);  //更改填充颜色
   while(s.top != s.base){  //把栈里面的正确路径用绿色方块画出
      p.y = GetTop(s);
      Pop(s);
      p.x = GetTop(s);
      Pop(s);
      fillrectangle(p.y*30,p.x*30,p.y*30+30,p.x*30+30);
   }
   _getch();              // 按任意键继续
   closegraph();          // 关闭绘图窗口
   return 0;
 }

最终效果：

嗯,可还行？

可不行，动态演示了解一下？

END