永发信息网

用栈实现迷宫的问题

答案:1  悬赏:10  手机版
解决时间 2021-05-11 00:04

#include <iostream.h>

#include <conio.h>

const int m = 9;

const int n = 9;

const

int maze[m+2][n+2] = {{0,0,0,0,0,0,0,0,0,0,0},

{0,1,0,0,0,0,1,0,1,0,0},

{0,0,1,0,0,1,0,1,1,0,0},

{0,0,0,1,0,0,1,0,0,0,0},

{0,0,1,0,0,0,1,0,0,0,0},

{0,0,0,1,0,1,0,1,0,0,0},

{0,0,0,0,1,0,0,1,0,0,0},

{0,0,1,0,1,0,1,0,0,0,0},

{0,0,0,1,0,0,0,1,1,0,0},

{0,0,0,0,0,0,0,0,0,1,0},

{0,0,0,0,0,0,0,0,0,0,0}};

typedef

struct node

{ int ipos,jpos; // 表示路径上某点的位置

int direct[8]; // 表示周围8个方向的可能探索信息

struct node *next; // 指向前一个栈结点

}node_type; // 探索路径时使用的链栈结点类型

typedef

struct postp

{ int ipos,jpos;

struct postp *next;

}pos_type; // 回溯路径时使用的链栈的结点类型

node_type *top; // 指向探索栈栈顶的指针

pos_type *pos_top; // 指向路径栈栈顶的指针

void init() // 初始化探索栈

{ top=new node_type;

top->ipos=1;

top->jpos=1;

top->direct[0]=maze[0][0];

top->direct[1]=maze[0][1];

top->direct[2]=maze[0][2];

top->direct[3]=maze[1][0];

top->direct[4]=maze[1][2];

top->direct[5]=maze[2][0];

top->direct[6]=maze[2][1];

top->direct[7]=maze[2][2];

top->next=NULL;

}

void check_cycle(int ii, int jj, node_type *newp) // 确认当前位置周围某点为不可探索

{ node_type *p=top;

while((p!=NULL)&&(!((p->ipos==ii)&&(p->jpos==jj)))) // 遍历栈

p=p->next; // 确认该点是否已入栈

if(p!=NULL)

switch(newp->ipos-ii)

{ case 1: switch(newp->jpos-jj)

{ case 1: newp->direct[0]=0; break;

case 0: newp->direct[1]=0; break;

case -1: newp->direct[2]=0;

}

break;

case 0: switch(newp->jpos-jj)

{ case 1: newp->direct[3]=0; break;

case -1: newp->direct[4]=0;

}

break;

case -1: switch(newp->jpos-jj)

{ case 1: newp->direct[5]=0; break;

case 0: newp->direct[6]=0; break;

case -1: newp->direct[7]=0;

}

}

}

void push(int ii, int jj) // 前进一步时的入栈

{ node_type *p;

p=new node_type;

p->ipos=ii;

p->jpos=jj;

p->direct[0]=maze[ii-1][jj-1];

p->direct[1]=maze[ii-1][jj];

p->direct[2]=maze[ii-1][jj+1];

p->direct[3]=maze[ii][jj-1];

p->direct[4]=maze[ii][jj+1];

p->direct[5]=maze[ii+1][jj-1];

p->direct[6]=maze[ii+1][jj];

p->direct[7]=maze[ii+1][jj+1];

check_cycle(ii-1,jj-1,p);

check_cycle(ii-1,jj,p);

check_cycle(ii-1,jj+1,p);

check_cycle(ii,jj-1,p);

check_cycle(ii,jj+1,p);

check_cycle(ii+1,jj-1,p);

check_cycle(ii+1,jj,p);

check_cycle(ii+1,jj+1,p);

p->next=top;

top=p;

}

void pop() // 排除当前点的出栈

{ node_type *p;

p=top;

top=p->next;

delete p;

}

void show_maze() // 显示迷宫

{ int i,j;

cout<<"The maze is showed as below (1 --- possible pathway): \n";

for(i=1; i<m+1; i++)

{ cout<<" ";

for(j=1; j<n+1; j++) cout<<maze[i][j]<<' ';

cout<<endl;

}

}

void show_pathway() // 显示走出迷宫的路径

{

初始化路径栈;

当探索栈非空, 重复下列操作

{

将探索栈顶出栈的点信息写入新建的路径栈结点;

}

当路径栈非空, 重复下列操作

{

输出路径栈栈顶出栈的点信息;

}

}

void main()

{ int i;

show_maze();

init();

while((top!=NULL)&&(!((top->ipos==m)&&(top->jpos==n))))

{ for(i=0; i<8; i++)

if(top->direct[i]==1)

{ top->direct[i]=0;

break;

}

switch(i)

{ case 0: push(top->ipos-1,top->jpos-1); break;

case 1: push(top->ipos-1,top->jpos); break;

case 2: push(top->ipos-1,top->jpos+1); break;

case 3: push(top->ipos,top->jpos-1); break;

case 4: push(top->ipos,top->jpos+1); break;

case 5: push(top->ipos+1,top->jpos-1); break;

case 6: push(top->ipos+1,top->jpos); break;

case 7: push(top->ipos+1,top->jpos+1); break;

default: pop();

}

}

if(top!=NULL)

{ cout<<"The pathway is: \n";

show_pathway();

}

else

cout<<"There is no pathway through the maze.\n";

getch();

}

最佳答案
你好。
很幸运看到你的问题。
但是又很遗憾到现在还没有人回答你的问题。也可能你现在已经在别的地方找到了答案,那就得恭喜你啦。
可能是你问的问题有些专业了,没人会。或者别人没有遇到或者接触过你的问题,所以帮不了你。建议你去问题的相关论坛去求助,那里的人通常比较多,也比较热心,可能能快点帮你解决问题。
希望我的回答也能够帮到你!
祝你好运~!
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
男生健身房运动穿什么,去健身房应该穿什么衣
windows mobile 和android选哪个好!纠结
手机有时候进电话响一下就自动关机是什么原因
同一根网线为什么有的电脑可以联上网有的却不
一个花心的男人,为什么在能得到你的时候不去
乐土粗糙的皮在哪个地图,坐标
奥比岛的小精灵如何到二级
今年长沙拉布拉多成犬的行市如何。
我是油性皮肤,洗过脸不到1小时就出油,这是
我为什么看见漂亮女孩子不敢和她对眼呢!!是
谁有NOD32激活码
显示 高压95 低压59 脉搏数81正常吗? 最近还
爱情的英语句子,寻关于爱情的英语句子
《总有一种力量让我们感动》中家里人的不同希
谁能传我个VRay150RC5_max9?
推荐资讯
静不下心来看书怎么办?
为什么我的空间打不开那些视频了,农场也打不
DNF无法登陆,急啊!!!
什么小说好看啊!!!
怎样才可以样问问得到更多的经验???
我家的地下城与勇士最近更新一旦到了17.44MB
上海南站到虹口足球场夜里怎么走
为什么嘴角会生疮
问道里的80的法装金套一般要好多钱
为什么男人就怎么累、
求梦幻西游抓鬼所有旗帜坐标
八个月的婴儿食谱
正方形一边上任一点到这个正方形两条对角线的
阴历怎么看 ?