注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

迷宫---好难啊  

2014-10-01 21:20:09|  分类: 数据结构---严老 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

struct PostType
{
int x;
int y;
};
const int Max=25;
int m[Max][Max];
int cur_step=1;
struct StackType//栈中的元素的类型
{
int order;//走的顺序号!
PostType seat;// 通道块在路径上的"序号"
int dir; // 从此通道块走向下一通道块的"方

bool Pass(PostType e)
{
if(m[e.x][e.y]==1)
{
return true;
}
return false;
}

void FootPrint(PostType e)
{
m[e.x][e.y]=cur_step;// 使迷宫m的e点的序号变为足迹(curstep)
}

void MarkCant(PostType e)
{
m[e.x][e.y]=-1;//,不能通过路径为-1
}

PostType NextPos(PostType e,int dir)
{ // 根据当前位置及移动方向,返回下一位置
PostType direc[4]={{0,1},{1,0},{0,-1},{-1,0}}; // {行增量,列增量}
// 移动方向,依次为东南西北
e.x+=direc[dir].x;
e.y+=direc[dir].y;
return e;
}

bool MazePath(PostType start ,PostType end)
{
SqStack S;
PostType cur_pos;
InitStack(S);
cur_pos=start;
StackType e;
do
{
if(Pass(cur_pos))
{
FootPrint(cur_pos);
e.order=cur_step;
e.seat.x=cur_pos.x;
e.seat.y=cur_pos.y;
e.dir=0;//前进的方向!
Push(S,e);
cur_step++;
if(cur_pos.x==end.x&&cur_pos.y==end.y)
{
return true;
}
cur_pos=NextPos(cur_pos,e.dir);
}
else//不能通过啊
{
if(!IsEmpty(S))
{
Pop(S,e);
cur_step--;
while(e.dir==3&&!IsEmpty(S))//有些时候我们可能会退很多的步!
{
MarkCant(e.seat);//不能走的路啊!
Pop(S,e);
cur_step--;
}
if(e.dir<3)// 没到最后一个方向(北)
{
e.dir++;
Push(S,e);
cur_step++;
cur_pos=NextPos(e.seat,e.dir);

}

}

}
}while(!IsEmpty(S));
}

主函数:

void Print(int x,int y)
{ // 输出迷宫的解
int i,j;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
printf("%3d",m[i][j]);
printf("\n");
}
}

int main()
{
PostType begin,end;
int i,j,x,y,x1,y1;
printf("请输入迷宫的行数,列数(包括外墙):");
scanf("%d,%d",&x,&y);
for(i=0;i<x;i++) // 定义周边值为0(同墙)
{
m[0][i]=0; // 行周边
m[x-1][i]=0;
}
for(j=1;j<y-1;j++)
{
m[j][0]=0; // 列周边
m[j][y-1]=0;
}
for(i=1;i<x-1;i++)
for(j=1;j<y-1;j++)
m[i][j]=1; // 定义通道初值为1
printf("请输入迷宫内墙单元数:");
scanf("%d",&j);
printf("请依次输入迷宫内墙每个单元的行数,列数:\n");
for(i=1;i<=j;i++)
{
scanf("%d,%d",&x1,&y1);
m[x1][y1]=0; // 定义墙的值为0
}
printf("迷宫结构如下:\n");
Print(x,y);
printf("请输入起点的行数,列数:");
scanf("%d,%d",&begin.x,&begin.y);
printf("请输入终点的行数,列数:");
scanf("%d,%d",&end.x,&end.y);
if(MazePath(begin,end)) // 求得一条通路
{
printf("此迷宫从入口到出口的一条路径如下:\n");
Print(x,y); // 输出此通路
}
else
printf("此迷宫没有从入口到出口的路径\n");
return 0;
}



  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017