我心飞翔

有事不慌,无事不荒,有容乃大,无欲则刚,以德立纲,外圆内方。

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 9 文章 :: 13 评论 :: 0 Trackbacks

//base.h
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;


//stack.h
#define STACK_INIT_SIZE 100 //存储空间初始量
#define STACK_INCREMENT 10//存储空间初始增量
typedef struct
{
 int r;
 int c;
}PostType;//坐标位置  迷宫的r行c列
typedef struct
{
 int ord;//通道块在路径上的序号
 PostType seat;//通道块的当前坐标位置
 int di;//通道块指向下一通道块的方向
}SElemType;//栈元素的类型
typedef struct
{
 SElemType *base;//栈底指针
 SElemType *top;//栈顶指针
 int stacksize;//栈的最大容量
}Stack;//栈的类型

Status InitStack(Stack &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;
}//InitStack

Status StackEmpty(Stack S)
//判断栈是否为空,如果为空返回TRUE,否则返回FALSE
{
 if(S.top==S.base)
  return TRUE;
  return FALSE;
}//StackEmpty

Status Push(Stack &S,SElemType e)
//插入元素为e的栈顶元素
{
 if(S.top-S.base>=S.stacksize)
 {
  S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));
       if(!S.base)
       exit(OVERFLOW);
    S.top=S.base+S.stacksize;
    S.stacksize+=STACK_INCREMENT;
 }
 *S.top++=e;
 return OK;
}//Push

Status Pop(Stack &S,SElemType &e)
//删除栈顶元素存入e
{
 if(S.top==S.base)
  return ERROR;
 e=*--S.top;
 return OK;
}//Pop

Status DestroyStack(Stack &S)
//销毁栈
{
 free(S.base);
 S.top=S.base;
 return OK;
}//DestroyStack


//maze.cpp
#define MAXLEN 20//迷宫包括外墙最大行列数目
typedef struct{
         int r;
         int c;
         char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#'
}MazeType;   //迷宫类型

Status InitMaze(MazeType &maze){
//初始化迷宫若成功返回TRUE,否则返回FALSE
         int m,n,i,j,k=1;
         printf("输入迷口的行数和列数: ");
         scanf("%d%d",&maze.r,&maze.c); //迷宫行和列数
         for(i=0;i<=maze.c+1;i++){//迷宫行外墙
                   maze.adr[0][i]='#';
                   maze.adr[maze.r+1][i]='#';
         }//for
         for(i=0;i<=maze.r+1;i++){//迷宫列外墙
                  maze.adr[i][0]='#';
                   maze.adr[i][maze.c+1]='#';
         }
         for(i=1;i<=maze.r;i++)
                   for(j=1;j<=maze.c;j++)
                            maze.adr[i][j]=' ';//初始化迷宫
         printf("输入障碍物%d的坐标(以坐标(0,0)结束输入): ",k);
         scanf("%d%d",&m,&n);//接收障碍的坐标
   k++;
       while(m!=0)
    {
                   if(m>maze.r || n>maze.c)//越界
                        exit(ERROR);
                   maze.adr[m][n]='#';//迷宫障碍用'#'标记
                   printf("输入障碍物%d的坐标(以坐标(0,0)结束输入): ",k);
                   scanf("%d%d",&m,&n);
       k++;
        }
         return OK;
}//InitMaze        

Status Pass(MazeType maze,PostType curpos){
//当前位置可通则返回TURE,否则返回FALSE
         if(maze.adr[curpos.r][curpos.c]==' ')//可通
                   return TRUE;
         else
                   return FALSE;
}//Pass

Status FootPrint(MazeType &maze,PostType curpos){
//若走过并且可通返回TRUE,否则返回FALSE
//在返回之前销毁栈S
         maze.adr[curpos.r][curpos.c]='*';//"*"表示可通
         return OK;
}//FootPrint

PostType NextPos(PostType &curpos,int i){
//指示并返回下一位置的坐标
         PostType cpos;
         cpos=curpos;
         switch(i){        //1.2.3.4分别表示东,南,西,北方向
                   case 1 : cpos.c+=1; break;
                   case 2 : cpos.r+=1; break;
                   case 3 : cpos.c-=1; break;
                   case 4 : cpos.r-=1; break;
                   default: exit(ERROR); 
         }
         return cpos;
}//Nextpos

Status MarkPrint(MazeType &maze,PostType curpos){
//曾走过但不是通路标记并返回OK
         maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
         return OK;
}//MarkPrint

void PrintMaze(MazeType &maze)
//将最后标记好的迷宫输出
{
 int i,j;
 printf("\n输出迷宫的路径:\n");
 for(i=0;i<=maze.c+1;i++)
  printf("%4d",i);//输出列数
 printf("\n");
 for(i=0;i<=maze.r+1;i++)
 {
  printf("%d",i);//输出行数
  for(j=0;j<=maze.c+1;j++)
   printf("%4c",maze.adr[i][j]);//输出迷宫
  printf("\n");
 }
}//PrintMaze


Status MazePath(MazeType &maze,PostType start,PostType end)
//若迷宫从入口start到end的通道则求得一条存放在栈中
{
 Stack S;//初始化栈
 PostType curpos;
 int curstep;
 SElemType e;
 InitStack(S);
 curpos=start;
 curstep=1;
 do
 {
  if(Pass(maze,curpos))//当前位置可通过而未曾走过留下足迹
  {
   FootPrint(maze,curpos);
   e.ord=curstep;e.seat=curpos;e.di=1;
   Push(S,e);//加入栈路径中
     if(curpos.r==end.r && curpos.c==end.c)//到达出口返回TRUE
    {
    if(!DestroyStack(S))
    exit(OVERFLOW);
       else return TRUE;
    }
     else
      {
    curpos=NextPos(curpos,1);//下一位置是当前位置
    curstep++;//探索下一步
     }
  }//if
  else//当前位置不能通过
  {
   if(!StackEmpty(S))
   {
    Pop(S,e);//提取前一位置
    while (e.di==4 && !StackEmpty(S))//4个方向都不能通过则留下记号@  提取前一个位置进行判断是否是能通过
    {
     MarkPrint(maze,e.seat);
     Pop(S,e);
    }
    if(e.di<4)//换下一个方向探索  设定当前位置为该新方向上的邻位 
    {
     e.di++;
     Push(S,e);
     curpos=NextPos(e.seat,e.di);
    }
   }//if
  }
 }while(!StackEmpty(S));
 if(!DestroyStack(S))
  exit(ERROR);
 else return FALSE;
}//MazePath


void main()
{
 MazeType maze;
 PostType start,end;
 char c;
 do
 {
  printf("----------找一条迷宫的路径-------------\n");
  if(!InitMaze(maze))
  {
   printf("\n 初始化迷宫失败!!!");
   exit(ERROR);
  }
  do
  {
   printf("\n请输入入口的坐标:");
    scanf("%d%d",&start.r,&start.c);//输入入口坐标
   if(start.r>maze.r || start.c>maze.c)
    printf("\n输入错误,请重新输入入口的坐标!!\n");
   continue;
  }
  while (start.r>maze.r || start.c>maze.c);
  do
  {
   printf("\n请输入出口的坐标:");//输入出口的坐标
   scanf("%d%d",&end.r,&end.c);
   if(end.r>maze.r || end.c>maze.c)
    printf("\n输入错误,请重新输入出口坐标!!\n");
   continue;
  }
  while (end.r>maze.r || end.c>maze.c);
  if(!MazePath(maze,start,end))
   printf("\n不能找到一条路径!!!\n");
  else PrintMaze(maze);//输出迷宫
  printf("是否要继续?(y/n):");
  scanf("%s",&c);
 }
 while (c=='y' || c=='Y');
}//main

posted on 2005-10-19 20:47 无情雨 阅读(1862) 评论(3)  编辑 收藏 引用 所属分类: 数据结构

评论

# re: 迷宫的求解(数据结构的栈运用) 2006-06-12 17:22 Hking
不能求解。  回复  更多评论
  

# re: 迷宫的求解(数据结构的栈运用) 2007-09-25 16:41 zsc
程序无语法错误,但是不能求解!!!!!!  回复  更多评论
  

# re: 迷宫的求解(数据结构的栈运用) 2008-09-26 09:29 Tina
在文件头加上#include "stdafx.h"即可运行  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理