C++走迷宫算法实现

C/C++语言基础

下载此实例

开发语言：C/C++
实例大小：1.02M
下载次数：7
浏览次数：49
发布时间：2024-09-20
实例类别：C/C++语言基础
发布人：Joezhoushen
文件格式：.zip
所需积分：2

相关标签：迷宫算法 c++ 走迷宫实现迷宫

网友评论举报投诉收藏该页

下载此实例预览此实例

实例介绍

迷宫迷宫算法堆栈c链表it 分类： C/C 技术
迷宫图案，白色代表通道，黑色代表墙。
迷宫入口坐标(1,1),出口坐标(8,8)
0 1 2 3 4 5 6 7 8 9
0■■■■■■■■■■
1■□□■□□□■□■
2■□□■□□□■□■
3■□□□□■■□□■
4■□■■■□□□□■
5■□□□■□□□□■
6■□■□□□■□□■
7■□■■■□■■□■
8■■□□□□□□□■
9■■■■■■■■■■

程序源代码(VC 6.0下编译通过)

# include <iostream>

using namespace std;

const int SIZE_X=10;
const int SIZE_Y=10;

//data struct
struct mPoint
{
int x;
int y;
bool can_move_to;
mPoint(int rx=0,int ry=0,bool rcan_move_to=false)
{
x=rx;
y=ry;
can_move_to=rcan_move_to;
next=NULL;
}
mPoint *next;
};

//function declaration
class mStack
{
public:
mStack();//constructor
int push(mPoint point);
mPoint pop();
int getLength();
mPoint getTop();
void printStack();
private:
mPoint *base;//base pointer
mPoint *top; //top pointer
int length; //length of stack
};

int main()
{
mPoint mpArray[SIZE_X][SIZE_Y];
bool initArray[SIZE_X][SIZE_Y]={{false,false,false,false,false,false,false,false,false,false},

{false,true ,true ,false,true ,true ,true ,false,true ,false},
{false,true ,true ,false,true ,true ,true ,false,true ,false},
{false,true ,true ,true ,true ,false,false,true ,true ,false},
{false,true ,false,false,false,true ,true ,true ,true ,false},
{false,true ,true ,true ,false,true ,true ,true ,true ,false},
{false,true ,false,true ,true ,true ,false,true ,true ,false},
{false,true ,false,false,false,true ,false,false,true ,false},
{false,false,true ,true ,true ,true ,true ,true ,true ,false},
{false,false,false,false,false,false,false,false,false,false}};//迷宫矩阵
for(int i=0;i<SIZE_X;i )//init
for(int j=0;j<SIZE_Y;j )
{
mpArray[i][j].x=i;
mpArray[i][j].y=j;
mpArray[i][j].can_move_to=initArray[i][j];
}
mPoint startp(1,1,true);//entry
mPoint endp(8,8,true); //exit

mStack mpath;
mpath.push(startp);

mPoint mp=startp;
while(true)
{
if(mp.x==endp.x && mp.y==endp.y)
break;//success
if(mpArray[mp.x 1][mp.y].can_move_to)//search down
{
mpArray[mp.x 1][mp.y].can_move_to=false;
mpath.push(mPoint(mp.x 1,mp.y));
mp=mpArray[mp.x 1][mp.y];
continue;
}
if(mpArray[mp.x-1][mp.y].can_move_to)//search up
{
mpArray[mp.x-1][mp.y].can_move_to=false;
mpath.push(mPoint(mp.x-1,mp.y));
mp=mpArray[mp.x-1][mp.y];
continue;
}
if(mpArray[mp.x][mp.y 1].can_move_to)//search right
{
mpArray[mp.x][mp.y 1].can_move_to=false;
mpath.push(mPoint(mp.x,mp.y 1));
mp=mpArray[mp.x][mp.y 1];
continue;
}
if(mpArray[mp.x][mp.y-1].can_move_to)//serch left
{
mpArray[mp.x][mp.y-1].can_move_to=false;
mpath.push(mPoint(mp.x,mp.y-1));
mp=mpArray[mp.x][mp.y-1];
continue;
}
if(0==mpath.getLength())
{
cout<<"No path!"<<endl;
return -1;
}
mpath.pop();
mp=mpath.getTop();
}
cout<<"Path:"<<endl;
mpath.printStack();//ouput path

return 0;
}

mStack::mStack()
{
length=0;
base=NULL;
top=NULL;
}
int mStack::push(mPoint point)
{
mPoint *mpNode=new mPoint();
*mpNode=point;
if(length==0)
top=base=mpNode;
else
{
top->next=mpNode;
top=mpNode;
}
return length;
}
mPoint mStack::getTop()
{
return *top;
}
mPoint mStack::pop()
{
if(length<=0)
return NULL;
mPoint retPoint=*top;
top=base;
while(top->next!=NULL)
{
if(top->next->next==NULL)
{
delete(top->next);
top->next=NULL;
break;
}
top=top->next;
}
if(length==1)
{
delete(base);
base=top=NULL;
}
length--;
return retPoint;
}

int mStack::getLength()
{
return length;
}
void mStack::printStack()
{
mPoint *p=base;
while(p!=NULL)
{
cout<<"("<<p->x<<","<<p->y<<")"<<endl;
p=p->next;
}

}

本程序堆栈用单向动态链表实现，当然可以用其他数据结构，比如双向链表。

程序输出结果：

Path:
(1,1)
(2,1)
(3,1)
(4,1)
(5,1)
(5,2)
(5,3)
(6,3)
(6,4)
(6,5)
(7,5)
(8,5)
(8,6)
(8,7)
(8,8)

标签： 迷宫算法 c++ 走迷宫实现迷宫

实例下载地址