用C++实现寻找迷宫里最短路线

起点由我给定的（x,y），终点是（1，1）迷宫也是已知的一个21*21的二维数组，数组中每一项的值：1表示墙，0表示路
最后用一个链表储存下每一步的动作（1234分别代表向上下左右）要求走过的总步数最小
我要详细的源代码
或者把问题简化一下，不要用链表储存每一步的动作，就储存第一步的方向就行了，可以考虑从终点开始搜索，然后记下最后一步

你找 QQ为85141512 的QQ空间里有 ，那个是我的

我是公司的网，上不了QQ抱歉。

有什么疑问发到百度我的消息里

都是数据结构的问题

我找到了，贴过来:

#include<iostream.h>
#include <stdlib.h>
#include<iomanip.h>
#define STACK_INIT_SIZE 100 //初始栈大小
#define STACKINCREAMENT 10 //添加栈的长度
#define SIZE_OF_MAPH 20 //迷宫高度
#define SIZE_OF_MAPW 20 //迷宫长度

////////////////////////////////////////////////////////////////////////////////
// 结构体名称：MazeCell
// 功能：用来描述迷宫组成单元的信息
// 成员：Pass: 当Pass为1时，表示导通块；为0则表示障碍块；
// Footprint: 当 Footprint为1时，表示留下足迹，反之，表示未经此地。
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
int Pass;
bool Footprint;
}MazeCell;

////////////////////////////////////////////////////////////////////////////////
// 结构体名称：SElemType
// 功能： 此为栈的元素，用来表示当前位置，（栈用来描述当前路径）
// 成员： ord: 通道块的序号
// x : 当前位置的横坐标
// y : 当前位置的纵坐标
// di : 搜索方向 1向东，2向南，3向西，4向北
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
int ord;
int x;
int y;
int di;
}SElemType;

////////////////////////////////////////////////////////////////////////////////
// 结构体名称： SqTack
// 功能： 此为栈，用来记录当前路径
// 成员： *base 栈底指针，指向起点
// *top 栈顶指针，指向路径的末点
// stacksize 栈的容量
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

////////////////////////////////////////////////////////////////////////////////
// 结构体名称： Seat
// 功能： 用来记录迷宫坐标，此结构体为中间变量，纯粹为方便编程而建立
// 成员： x: 用来记录横坐标
// y: 用来记录纵坐标
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
int x;
int y;
}Seat;

////////////////////////////////////////////////////////////////////////////////
// 函数名称： InitStack
// 功能： 此函数用于初始化一个栈，即在类存中找一块大小为STACK_INIT_SIZE个栈
// 元素的空间,将其首址赋给栈底指针，此时栈顶指针与栈底指针重合。栈的容
// 量为 STACK_INIT_SIZE。操作成功则函数返回1，若类存空间不足，函数返回
// 0，表示初始化失败。
// 函数参数： SqStack &S
// 函数返回值类型： bool
////////////////////////////////////////////////////////////////////////////////
bool InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
{
return 0;
}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 0;
}

////////////////////////////////////////////////////////////////////////////////
// 函数名称： BuideMaze
// 功能： 此函数的功能是用于根据用户要求建立一个迷宫地图，将用户输入的整形数组
// 形状给迷宫数组
//
// 函数参数： MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP]
// Seat &start 起点坐标
// Seat &end 终点坐标
// 函数返回值类型： bool 建立成功则返回1，反之返回0。
////////////////////////////////////////////////////////////////////////////////
void BuideMaze(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],int ma[SIZE_OF_MAPH][SIZE_OF_MAPW])
{
for(int i=0;i<SIZE_OF_MAPH;i++)
{
for(int j=0;j<SIZE_OF_MAPW;j++)
{
Map[i][j].Pass=ma[i][j];
Map[i][j].Footprint=0;
}
}
}

////////////////////////////////////////////////////////////////////////////////
// 函数名称： Pass
// 功能： 此函数用于判断当前点是否可通，如果可通则返回1，反之返回0。
// 所谓可通是指当前位置为导通块并且当前位置没有留下脚印。
// 函数参数： Seat curpos 当前块的坐标
// MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP] 迷宫地图
// 函数返回值类型： bool 若当前块可通则返回1，反之则返回0。
////////////////////////////////////////////////////////////////////////////////
bool Pass(Seat curpos,MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW])
{
if(Map[curpos.x][curpos.y].Pass==0)
{
return 0;
}
else if(Map[curpos.x][curpos.y].Footprint==1)
{
return 0;
}
else
{
return 1;
}
}

////////////////////////////////////////////////////////////////////////////////
// 函数名称： FootPrint
// 功能： 此函数用于在当前路径下留下脚印。
// 函数参数： Seat curpos 当前坐标
// MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP] 迷宫地图
// 函数返回值类型： 无
////////////////////////////////////////////////////////////////////////////////
void FootPrint(Seat curpos,MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW])
{
Map[curpos.x][curpos.y].Footprint=1;
}

bool Push(SqStack &S,SElemType e)//栈插入函数
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(SElemType));
if(!S.base)
{
return 0;
}
S.top=S.base+S.stacksize;
S.stacksize=S.stacksize+STACKINCREAMENT;
}
*S.top++=e;
return 1;
}
bool Pop(SqStack &S,SElemType &e)//栈取出最上面的元素，将值给e
{
if(S.base==S.top)return false;
S.top--;
e=*S.top;
return true;
}

////////////////////////////////////////////////////////////////////////////////
// 函数名称： NextPos
// 功能： 此函数用于将坐标为x,y位置的di方向位置切换为当前位置。
// 函数参数： Seat curpos 当前坐标
// int di 方向
// int x,y 坐标
// 函数返回值类型： 无
////////////////////////////////////////////////////////////////////////////////
void NextPos(int x,int y,Seat &curpos,int di)
{
if(di==1)
{
curpos.y=y+1;
curpos.x=x;
}
else if(di==2)
{
curpos.x=x+1;
curpos.y=y;
}
else if(di==3)
{
curpos.y=y-1;
curpos.x=x;
}
else if(di==4)
{
curpos.x=x-1;
curpos.y=y;
}
}

///////////////////////////////////////////////////////////////////////////
// 函数名称： PutIn
// 功能： 向数组里输入元素
// 函数参数： int map[] 将得到的数组给map
// int Wei 迷宫的长度
// int Hig 迷宫的高度
// 函数返回值类型： 无
///////////////////////////////////////////////////////////////////////////
void PutIn(int map[],int &Wei,int &Hig)
{
int w,h;
cout<<"如果您想输入的迷宫大于所规定的大小，您只需修改SIZE_OF_MAPH和SIZE_OF_MAP"<<endl;
cout<<"请输入迷宫的长度(长度小于等于"<<SIZE_OF_MAPW-2<<")：";
cin>>w;
cout<<"请输入迷宫的高度(高度小于等于"<<SIZE_OF_MAPW-2<<")：";
cin>>h;
cout<<"1表示导通块；0表示障碍块"<<endl;
Wei=w;
Hig=h;
for(int i=0;i<SIZE_OF_MAPH;i++)
for(int j=0;j<SIZE_OF_MAPW;j++)
*(map+i*SIZE_OF_MAPW+j)=0;
for(int is=1;is<h+1;is++)
{
cout<<"请输入第"<<is<<"行:";
for(int js=1;js<w+1;js++)
{
int point;
cin>>point;
*(map+is*SIZE_OF_MAPW+js)=point;
}
cout<<endl;
}
}

///////////////////////////////////////////////////////////////////////////
// 函数名称： Display
// 功能： 用于显示栈中所有元素
// 函数参数： 无
// 函数返回值类型： 无
///////////////////////////////////////////////////////////////////////////
void Display(SqStack S)
{
int i=1;
SElemType *p;
p=S.base;
cout<<"从base到top:"<<endl;
cout<<"di搜索方向:di=1向东，di=2向南，di=3向西，di=4向北"<<endl;
while(p!=S.top) //从base到top打印元素
{
cout<<"第"<<i<<"步: ";
cout<<"("<<(*p).y;
cout<<","<<(*p).x;
cout<<","<<(*p).di<<")"<<endl;
p++;
i++;
}
}

void DisplayMaze(int ma[SIZE_OF_MAPH][SIZE_OF_MAPW],int w,int h)
{
cout<<"迷宫为(1代表可以通过；0代表不可以通过): "<<endl;
for(int i=0;i<h+2;i++)
{
for(int j=0;j<w+2;j++)
{
cout<<ma[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}

///////////////////////////////////////////////////////////////////////////
// 函数名称： MazePath
// 功能： 组织所有子函数，求解迷宫
// 函数参数： 无
// 函数返回值类型： int 迷宫有解则返回1，反之则返回0；
////////////////////////////////////////////////////////////////////////////
int MazePath(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],Seat start,Seat end)
{
SElemType e;
SqStack S; //定义一个栈
InitStack(S); //初始化栈
Seat curpos; //定义当前位置
int curstep; //计步器
curstep=1; //计步器计1
curpos.x=start.x; //
curpos.y=start.y; //当前位置设为起点
cout<<"起点是:"<<start.y<<" "<<start.x<<endl;
cout<<"终点是:"<<end.y<<" "<<end.x<<endl;

///////////////////////////////////////////////////////////////////////////
//
// 下面的循环是求解迷宫的核心程序

////////////////////////////////////////////////////////////////////////////
do
{
if(Pass(curpos,Map)) //如果当前块可通，则进行如下操作
{
FootPrint(curpos,Map); //留下脚印
e.ord=curstep; //记下计步器
e.x=curpos.x; //记下行数
e.y=curpos.y; //记下列数
e.di=1; //设一个方向为东方
Push(S,e); //压栈操作，将当前位置纳入当前路径
if(curpos.x==end.x&&curpos.y==end.y) //如果当前块为终点，进行如下操作
{ //
cout<<"ok!"; //
Display(S); //调用显示栈的子程序显示结果
return 1; //函数返回1
} //
else //如果当前位置不是终点，进行如下操作
{ //
NextPos(curpos.x,curpos.y,curpos,1); //切换东方向的位置为当前位置
curstep++; //计步器自增1
}
}//if
else
{
if(S.base!=S.top) //如果当前块不通，且栈不为空（说明还有解）
{
Pop(S,e); //将栈顶元素弹出进行观察
while(e.di==4&&(S.top-S.base)) //如果栈顶元素四方均不通
{
Pop(S,e); //弹出下一个栈顶元素进行观察
}//while
if(e.di<4) //如果栈顶元素还有其他方向没有走过
{ //
e.di++; //切换下一个方向为当前方向
Push(S,e); //压入栈
NextPos(e.x,e.y,curpos,e.di); //切换下一个方向位置为当前位置
}//if
}//if
}//else
}while(S.base!=S.top); //只要栈不空则说明有解，重复循环
cout<<"没找到路径"<<endl;
}

////////////////////////////////////////////////////////////////////////////////
// 函数名称： main
// 功能： 组织所有子函数，求解迷宫
// 函数参数： 无
// 函数返回值类型： bool 迷宫有解则返回1，反之则返回0；
//
////////////////////////////////////////////////////////////////////////////////
void main()
{
MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW]; //定义一个迷宫数组

int w,h;
int migong[SIZE_OF_MAPH][SIZE_OF_MAPW];
PutIn(migong[0],w,h);
BuideMaze(Map,migong); //调用建立迷宫的子函数
DisplayMaze(migong,w,h); //显示迷宫的形状
Seat start,end; //定义当前位置，起点位置，终点位置的结构体

cout<<"起点横坐标:";
cin>>start.y;
cout<<"起点纵坐标:";
cin>>start.x;
cout<<"终点横坐标:";
cin>>end.y;
cout<<"终点纵坐标:";
cin>>end.x;
MazePath(Map,start,end);
}

程序大部分分成函数了，你只要把函数的功能弄清楚了，就差不多了
祝你成功！我当时弄了3天才写出来的

广度优先遍历即可

我这几天刚写了一个，应该可以运行的。 #include<iostream.h> #include<process.h> template<class T> class Stack { private: int MaxNum; //栈的最大空间 int top; //栈顶 T *s; //栈的元素 public: //构造函数及析构函数 Stack(int n) { if(n<1) { cout<<"构造函数非法"<<endl; exit(0); } MaxNum=n; top=-1; s=new T [MaxNum]; if(!s) { exit(0); } } ~Stack() { delete []s; } bool IsFull() { if(top==MaxNum-1) return true; else return false; } bool IsEmpty() { if(top==-1) return true; else return false; } void Push(T x) { if(IsFull()) { cout<<"栈满了"<<endl; exit(0); } s[++top]=x; } T Pop() { if(IsEmpty()) { cout<<"栈空!"<<endl; exit(0); } return s[top--]; } }; #include"stack.h" #include<iostream.h> #define MAXLEN 10 struct PostType { int r; //行 int c; //列 }; struct SElemType { PostType seat; int di; //方向 }; struct MazeType { int r; int c; char adr[MAXLEN][MAXLEN]; //''表示未走过且可以走的,'*'表示已走过的 }; //10*10的迷宫类型 bool Pass(MazeType maze,PostType pos) { if(maze[pos.r][pos.c]=='') return true; else return false; } void FootPrint(MazeType &maze,PostType pos) { maze[pos.r][pos.c]='*'; } void NextPos(PostType &pos, int i) { //1.2.3.4分别表示东,南,西,北方向 switch(i) { case 1 : pos.c+=1; break; case 2 : pos.r+=1; break; case 3 : pos.c-=1; break; case 4 : pos.r-=1; break; default: exit(1); } } void MarkPrint(MazeType &maze,PostType pos) { maze[pos.r][pos.c]='@'; } bool MazePath(MazeType &maze,PostType start,PostType end) { PostType curpos; //当前扫描的点 SElemType e; int di; Stack<SElemType>S(200); curpos=start; //始终从东开始扫描 do { if(Pass(maze,curpos)) //看当前点是否可以通过 { //进栈，不能通过不能进栈 e.seat=curpos; e.di=1; S.Push(e); //并且标记已走过该路径 FootPrint(maze,curpos); //检查是否到达终点 if((curpos.r==end.r)&&(curpos.c==curpos.c)) { while(!S.IsEmpty()) { e=S.Pop(); cout<<e<<endl; } return true; } else { NextPos(curpos,1); //始终从东扫描 } } //end if else //无法通过 { e=S.Pop(); while(!S.IsEmpty()&&(e.di==4)) { MakePrint(maze,e.seat); //标记已走过但出栈的点 e=S.Pop(); } if(!S.IsEmpty()&&e.di<4) //可以修改方向 { curpos=e.seat; e.di++; //栈顶的点再次进栈 S.Push(e); //还必须再次求其下一个点 NextPos(curpos,1); } } //end else }while(!S.IsEmpty()); return false; }

其实应该 广搜 但基于迷宫不大 深搜也可以 至于你说的用链表储存，那一定是广搜的方法 可那样实现起来有点麻烦，基于简单的原则，用数组模拟就足够了 我比较喜欢深搜，这里可以加上A*算法，效果很不错。 但基于简单的原则，A*也省略了。。。。。 以下是经过重重省略的代码(而且未经编译,仅给主要过程): bool deepFirstSearch(int x,int y,int s[22][22],int path,int deep){ if (deep<path || s[x][y]==1) return false; if (x==1 && y==1) return true; if(deepFirstSearch(x+1,y,s,path+1,deep))return true; if(deepFirstSearch(x-1,y,s,path+1,deep))return true; if(deepFirstSearch(x,y+1,s,path+1,deep))return true; if(deepFirstSearch(x,y-1,s,path+1,deep))return true; return fasle; } int main(){ for(deep=1;!deepFirstSearch(x,y,s,0,deep);deep++); cout<<deep<<endl; } 这个就是传闻中的 A 算法，也叫迭代加深，是一种深搜模拟广搜的算法 真怀念呀，最近写这个A也是几年前了，那时候刚开始接触编程 再多加一句，那迷宫的边界都要给赋值成1呀，相当于外墙

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息