?关于求解迷宫的所有路径
下面是我用栈写的一个求解迷宫所有路径的程序,运行后的结果没达到要求,我自己找不出错误,希望大家帮帮忙!(1,1) (2,1) (2,2) (3,2) (3,3)
(1,1) (2,1) (2,2) (2,3) (3,3) (Press any key to continue 这是运行结果
源程序:
#include<iostream>
using namespace std;
struct Position
//迷宫方格的坐标
{
int row,col;
};
struct Linknode
//栈的结点
{
Position date;
Linknode* next;
};
class Stack
//栈
{
private:
Linknode* top;
public:
Stack()
{ top=NULL; }
bool Empty();
Position Gettop();
void Push(Position &p);
Position Pop();
};
bool Stack::Empty()
{
if( top==NULL )
return true;
else
return false;
}
Position Stack::Gettop()
{
Position p;
p.row=-2;p.col=-2;
if(!Empty())
{
p=top->date;
}
return p;
}
void Stack::Push(Position &p)
{
Linknode* q = new Linknode;
(q->date).row=p.row;
(q->date).col=p.col;
q->next=top;
top=q;
}
Position Stack::Pop()
{
Position q;
q.row=-2;q.col=-2;
if(!Empty())
{
Linknode* p=top;
q.row=(top->date).row;
q.col=(top->date).col;
top=top->next;
delete p;
}
return q;
}
void Printpath(Stack s)
//打印路径的函数
{
Position q;
while(!s.Empty())
{
q=s.Pop();
cout<<"("<<q.row<<","<<q.col<<")"<<" ";
}
cout<<endl;
}
void main()
{
Position offset[4];//初始化相对位移
offset[0].row=0;offset[0].col=1;//右
offset[1].row=1;offset[1].col=0;//下
offset[2].row=0;offset[2].col=-1;//左
offset[3].row=-1;offset[3].col=0;//上
Position start,end,move;//迷宫中的入口,出口,移动
start.row=1;start.col=1;
end.row=3;end.col=3;
Stack s1,s2,s3,s4;
int point[5][5]=
{//初始化迷宫
{1,1,1,1,1},
{1,0,0,1,1},
{1,0,0,0,1},
{1,1,0,0,1},
{1,1,1,1,1}
};
s1.Push(start);
s2.Push(start);
point[1][1]=-1;//标识入口到达过
while(!s2.Empty())
{
Position p1,p2,p3;
p1=s1.Gettop();
p2=s2.Gettop();
if(!((p1.row==p2.row)&&(p1.col==p2.col)))
s1.Push(p2);
for(int i=0;i<4;i++)
{
int x=p2.row+offset[i].row;
int y=p2.col+offset[i].col;
if(point[x][y]==0)
{
start.row=x;start.col=y;
point[x][y]=-1;
s2.Push(start);
}
if((x==end.row)&&(y==end.col)&&(point[x][y]==-1))
{
start.row=x;start.col=y;
s1.Push(start);
while(!s1.Empty())
//调用Printpath()函数后栈中元素会被清空，两个While语句是保存S1和生成一个和S1中元素顺序相反的栈S3
{
p3=s1.Pop();
s3.Push(p3);
s4.Push(p3);
}
while(!s4.Empty())
{
p3=s4.Pop();
s1.Push(p3);
}
Printpath(s3);
while((s1.Gettop().row==s2.Gettop().row)&&(s1.Gettop().col==s2.Gettop().col)&&((s1.Gettop().row)!=-2))
//s1和s2中若栈顶元素相同则出栈
{
if(point[s1.Gettop().row][s1.Gettop().col]==-1)
point[s1.Gettop().row][s1.Gettop().col]=0;
move=s1.Pop();
move=s2.Pop();
}
i=4;
}
}
if((s1.Gettop().row==s2.Gettop().row)&&(s1.Gettop().col==s2.Gettop().col)&&((s1.Gettop().row)!=-2))
//处理碰到走不通时的情况
{
move=s1.Pop();
move=s2.Pop();
}
}
}
