Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1430580
  • 博文数量: 613
  • 博客积分: 11499
  • 博客等级: 上将
  • 技术积分: 5511
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 19:27
  • 认证徽章:
文章分类

全部博文(613)

文章存档

2016年(5)

2015年(18)

2014年(12)

2013年(16)

2012年(300)

2011年(45)

2010年(37)

2009年(79)

2008年(101)

分类: LINUX

2010-06-13 14:07:32

/************************************************************************/
/*
题目:可以输入一个任意大小的迷宫数据,用非递归的方法求出一条走出迷宫的路径,并将路径输出;
最好有注释、储结构、基本算法(可以使用程序流程图)、源程序、测试数据和结果、算法的时间复杂度、
另外可以提出算法的改进方法;
测试一:
8 8
1,1
7,7
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1
请输入迷宫的行数 m=8
请输入迷宫的列数 n=8
请输入迷宫的各行各列:
用空格隔开,0代表路,1代表墙
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
你建立的迷宫为o(∩_∩)o...
1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
输入入口的横坐标,纵坐标[逗号隔开]
1,1
输入出口的横坐标,纵坐标[逗号隔开]
5,5
没有找到可以走出此迷宫的路径

请输入迷宫的行数 m=8
请输入迷宫的列数 n=8
请输入迷宫的各行各列:
用空格隔开,0代表路,1代表墙
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1
你建立的迷宫为o(∩_∩)o...
1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 0 0 0 1 1
1 1 0 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
输入入口的横坐标,纵坐标[逗号隔开]
1,1
输入出口的横坐标,纵坐标[逗号隔开]
7,7
0=东 1=南 2=西 3=北 886为则走出迷宫
通路为:(行坐标,列坐标,方向)
-->(1,1,0)-->(1,2,0)-->(1,3,0)-->(1,4,1)-->(2,4,1)-->(3,4,1)-->(4,4,1)-->(5,4,1)
-->(6,4,1)-->(7,4,0)-->(7,5,0)-->(7,6,0)-->(7,7,886)请按任意键继续. . .
*/
/************************************************************************/
#include
#include
#define M 15
#define N 15
struct mark //定义迷宫内点的坐标类型
{
 int x;
 int y;
};
struct Element //"恋"栈元素,嘿嘿。。
{
 int x,y; //x行,y列
 int d; //d下一步的方向
};
typedef struct LStack //链栈
{
 struct Element elem;
 struct LStack *next;
} *PLStack;

/*************栈函数****************/
int InitStack(PLStack &S)//构造空栈
{
 S=NULL;
 return 1;
}
int StackEmpty(PLStack S)//判断栈是否为空
{
 if(S==NULL)
 {
  return 1;
 }
 else
 {
  return 0;
 }
}
int Push(PLStack &S, Element e)//压入新数据元素
{
 PLStack p;
 p=(PLStack)malloc(sizeof(LStack));
 p->elem=e;
 p->next=S;
 S=p;
 return 1;
}
int Pop(PLStack &S,Element &e) //栈顶元素出栈
{
 PLStack p;
 if(!StackEmpty(S))
 {
  e=S->elem;
  p=S;
  S=S->next;
  free(p);
  return 1;
 }
 else
 {
  return 0;
 }
}

/***************求迷宫路径函数***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
 int i,j,d;int a,b;
 struct Element elem;
 struct Element e;
 PLStack S1,S2;
 InitStack(S1);
 InitStack(S2);
 maze[start.x][start.y]=2; //入口点作上标记
 elem.x=start.x;
 elem.y=start.y;
 elem.d=-1; //开始为-1
 Push(S1,elem);
 while(!StackEmpty(S1)) //栈不为空 有路径可走
 {
  Pop(S1,elem);
  i=elem.x;
  j=elem.y;
  d=elem.d+1; //下一个方向 d=0\1\2\3分别代表东南北西
  while(d<4) //试探东南西北各个方向
  {
   a=i+diradd[d][0];
   b=j+diradd[d][1];
   /*优化算法*/
   if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
   {
    elem.x=i;
    elem.y=j;
    elem.d=d;
    Push(S1,elem);
    elem.x=a;
    elem.y=b;
    elem.d=886; //方向输出为-1 判断是否到了出口
    Push(S1,elem);
    printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");
    while(S1) //逆置序列 并输出迷宫路径序列
    {
     Pop(S1,e);
     Push(S2,e);
    }
    while(S2)
    {
     Pop(S2,e);
     printf("-->(%d,%d,%d)",e.x,e.y,e.d);
    }
    return; //跳出两层循环,本来用break,但发现出错,exit又会结束程序,选用return还是不错滴o(∩_∩)o...
   }
   if(maze[a][b]==0) //找到可以前进的非出口的点
   {
    maze[a][b]=2; //标记走过此点
    elem.x=i;
    elem.y=j;
    elem.d=d;
    Push(S1,elem); //当前位置入栈
    i=a; //下一点转化为当前点
    j=b;
    /*换一个点再从四个方向开始*/
    d=-1;
   }
   d++;
  }
 }
 printf("没有找到可以走出此迷宫的路径\n");
}

/*************建立迷宫*******************/
void initmaze(int maze[M][N])
{
 int i,j;
 int m,n; //迷宫行,列
 printf("请输入迷宫的行数 m=");
 scanf("%d",&m);
 printf("请输入迷宫的列数 n=");
 scanf("%d",&n);
 printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);
 for(i=1;i<=m;i++)
 {
  for(j=1;j<=n;j++)
  {
   scanf("%d",&maze[i][j]);
  }
 }
 printf("你建立的迷宫为o(∩_∩)o...\n");
 for(i=0;i<=m+1;i++) //加一圈围墙
 {
  maze[i][0]=1;
  maze[i][n+1]=1;
 }
 for(j=0;j<=n+1;j++)
 {
  maze[0][j]=1;
  maze[m+1][j]=1;
 }
 for(i=0;i<=m+1;i++) //输出迷宫
 {
  for(j=0;j<=n+1;j++)
  {
   printf("%d ",maze[i][j]);
  }
  printf("\n");
 }
}
int  main(char argc,char ** argv)
{
 int sto[M][N];
 struct mark start,end; //start,end入口和出口的坐标
 int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为南东北 西
 initmaze(sto);//建立迷宫
 printf("输入入口的横坐标,纵坐标[逗号隔开]\n");
 scanf("%d,%d",&start.x,&start.y);
 printf("输入出口的横坐标,纵坐标[逗号隔开]\n");
 scanf("%d,%d",&end.x,&end.y);
 MazePath(start,end,sto,add); //find path
 system("PAUSE");
 return 0;
}
阅读(976) | 评论(0) | 转发(0) |
0

上一篇:线性顺序表

下一篇:走迷宫(C++)

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册