migong.txt

迷宫的程序

#include<stdio.h>
#include<malloc.h>
#define STACK_INIT_SIZE 100

typedef struct
{
　int *base;
　int *top;
　int stacksize;
}sqstack;

int initstack(sqstack *s)
{
　　s->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
　　if(!s->base) return 0;
　　s->top=s->base;
　　s->stacksize=STACK_INIT_SIZE;
　　return 1;    
}

int push(sqstack *s,int e)
{
　if(s->top-s->base>=s->stacksize)
   {
　　　s->base=(int *)realloc(s->base,(s->stacksize+10)*sizeof(int));
　　　if(!s->base) return 0;
　　　s->top=s->base+s->stacksize;
　　　s->stacksize+=10;
   }
   *(s->top++)=e;
　return 1;
}

int gettop(sqstack *s)
{
　int e;
　e=*(s->top-1);
　return e;
}

int pop(sqstack *s)
{
　int e;
　e=*(--s->top);
　return e;
}
   

#include<iostream.h>
#include<string.h>

sqstack line;
char maze_map[9][9];  //实际为8*8的地图
int direction_row[4]={-1,0,1,0},direction_column[4]={0,1,0,-1};  //定下一步走的方向
int key=1;

void dim_maze_map()            //自定义绘制地图函数
{
　cout<<"~!~!~!~[注]~!~!~!~  :"<<endl;
　cout<<"        你必须在8*8的距阵中绘制地图[切记: 8*8] ! 迷宫的墙用'#'表示,路用' '表示,迷宫的四周必须是墙,起点在2,2处,终点在7,7处!"<<endl;
　cout<<endl;
　cout<<"开始绘制地图..."<<endl<<endl;
　for(int m=0;m<=7;m++)
　for(int n=0;n<=8;n++)        //由于getchar()需要接受换行,因此8*8的地图的列数为9列
　maze_map[m][n]=getchar();
}

void step_maze_map(int row,int column)  //寻找可走路径函数
{
　int ally,next_row,next_column;
　if(row==6&&column==6)    //走到目的则用开关结束所有未完递归函数中的循环
　　　key=0;
　else 
　{
　　for(int m=0;m<=3&&key==1;m++)
　　{
　　　next_row=row+direction_row[m];  //按“上,右,下,左,“的顺序默定下一步
　　　next_column=column+direction_column[m];
　　　if(maze_map[next_row][next_column]=='#'||maze_map[next_row][next_column]=='*');  //若下一步为墙或回路
　　　else 
　　　　{
    　ally=next_row*100+next_column; //将走过路的行列集合起来
    　push(&line,ally);  //将走过的路压栈
    　maze_map[next_row][next_column]='*'; //记录下已走过的步伐  
    　step_maze_map(next_row,next_column); //递归下一步
    }
　　　}
　　　if(m==4) //若四个方向都走满了 则此步走不通
　　　{
    maze_map[row][column]=' '; //消除记录的步伐
    pop(&line);  //弹出此步的栈
　　　}
　}
}

void print()  //打印迷宫走法函数
{
　　cout<<"迷宫走法示意图： "<<endl;
　　for(int i=0;i<=7;i++)
　　{
    cout<<"                         ";
    for(int j=0;j<=7;j++)
    {
       cout<<maze_map[i][j];
       if(j==7)
       cout<<endl;
         }
    }
}

int judge() //判断此迷宫可否走
{
  for(int i=0;i<=7;i++)
  for(int j=0;j<=7;j++)
  if(maze_map[i][j]=='*') //由与不可走的记录下的步伐会被还原，则地图上没有记录可断定迷宫不可走
      return 1;
  return 0;
}

void main()
{
   int row,column;
   dim_maze_map();
   maze_map[1][1]='*';
   push(&line,101);
   step_maze_map(1,1);
   if(judge())
   {
      print();
      cout<<endl<<endl;
      cout<<"此迷宫的路径为： "<<endl;
      while(*(line.base)>0) //栈中的内容若没有实际值,则结束循环
      {
    row=*(line.base)/100;
    column=*(line.base)%100;
    line.base++;
    cout<<row<<" "<<column<<"---->>>>";
      }
    }
   else cout<<"你将困死在这   ~_~  此迷宫永远为出路!"<<endl;
}