数字迷宫思考-上
----用栈的方法实现
数字迷宫游戏，可以用递归和栈的方法来实现穷举搜索通往出口的路径。实现的过程中，需要建立一个表示迷宫的二维数组，数组中的每个元素用0、1表示，0为此节点是通路，1表示断路，不能继续前行。迷宫的四周都是1表示的墙，只有一个入口和一个出口，每个结点都有八个方向可以搜索。游戏开始的时候，从入口进入，按“北->东北->…->西北”的逆时针方向依次搜索路径，当d方向的下一结点是0，则将当前节点入栈，并将当前节点标记为“1”走过，防止向前搜索失败回溯时再重复。当搜索到某个节点时，不能再继续向下，即进入了死胡同时，就需要回溯，将上一个节点出栈，并在上一节点的下一个方向上搜索，若8个方向都遍历完还没找到前进节点，则继续回溯…如果栈为空时，表示回到出发点，没有到达出口的路径。
在实现这个过程的时候，可以用顺序栈，也可以用链式栈。但是，如果顺序栈定义为模板类的时候，将路径节点入栈的时候，其过程是值入栈，而结构体又包含横纵坐标值和方向值，这样一来就会导致出栈时得到的是某一节点的横坐标值或纵坐标值或方向值(根据结构体的定义顺序而已，也即是结构体中最后定义的那个元素)。如果，路径是朝入口处开始搜索的方向(北向)不变一直走到出口(即没有出栈操作)，能找到出口，但却不能正常显示走过的路径节点信息。因此，用入栈地址的方式更加合理，即采用链式栈的方式。
由于栈的元素是先进后出，因此，在显示路径信息的时候，是从出口到入口的顺序。为了按入口到出口的顺序显示路径信息，需要将栈进行逆向排列。然而，栈是用模板类进行定义的，当结构体作为一种元素类型入栈时，模板类栈事先是不知道其具体类型的(即结构体包含多少元素信息)，因此，在定义链式栈时将栈顶指针设为公有，这多少有些违背了类隐藏的原则。因此，最好的办法还是不要用模板类链栈的定义。下面附上实现数字迷宫的c++源代码。
/**********************************************************
Copyright@2009-2011 by hank(SiChuan University)
***********************************************************/
//Node.h
#ifndef NODE_H
#define NODE_H
//数组元素节点类定义
#include<string.h>
#include<cstdlib>
struct offset
{
int a;
int b;
};
struct item
{
int x;
int y;
int dir;
};
#endif
/**********************************************************
Copyright@2009-2011 by hank(SiChuan University)
***********************************************************/
//ItStack.h
#ifndef LINKEDSTACK_H
#define LINKEDSTACK_H
//链式栈的类定义
#include<cstdlib>
#include<cassert>
template<class T>
struct LinkNode
{
T data;
LinkNode<T>* link;
LinkNode(LinkNode<T>* ptr=NULL):link(ptr){}
LinkNode(T item,LinkNode<T>* ptr=NULL):data(item),link(ptr){}
};
template<class T>
class LinkedStack
{
public:
LinkNode<T>* top;//暂时这样，方便后面的输出
LinkedStack(){top=NULL/*new LinkNode<T>*/;}//默认构造函数,初始化为NULL，怎么能是开辟空间呢!
//LinkedStack(LinkedStack<T>& LS);//拷贝构造函数，暂时不用，需要先逆转再逐个复制
~LinkedStack(){makeEmpty();delete top;}//析构函数
void makeEmpty();//清空栈，仅剩下栈头
int Length();//获取栈长度
LinkNode<T>* topPointer(){return top;}//取栈头指针
bool IsEmpty()const{return top==NULL?true:false;}//空否?
void push(T& x);//入栈
bool pop(/*const*/ T& x);//出栈
bool getTop(T& x)const;//取栈顶元素
void output();//显示栈元素
voidReverse();//逆转栈
};
#endif
/**********************************************************
Copyright@2009-2011 by hank(SiChuan University)
***********************************************************/
// ItStack.cpp
#include"ItStack.h"
//清空栈，仅剩下栈头
template<class T>
void LinkedStack<T>::makeEmpty()
{
LinkNode<T>* del;
while(top!=NULL)
{
del=top;
top=top->link;
delete /*top*/del;//怎么搞的哦，把top给delete了
}
}
/*************************************************/
//入栈,只要能开辟空间就能入栈，不存在栈慢的情况
template<class T>
void LinkedStack<T>::push(T& x)
{
LinkNode<T>* newNode;
newNode=new LinkNode<T>(x);
assert(newNode!=NULL);
newNode->link=top;
top=newNode;
}
/*************************************************/
//出栈，需要考虑空栈的情况
template<class T>
bool LinkedStack<T>::pop(/*const*/ T& x)//此处不宜const,因为后面元素要出栈，
{ //且出栈后需要进行修改
if(IsEmpty())
return false;
LinkNode<T>* del=top;
x=del->data;
top=del->link;
delete del;
return true;
}
/*************************************************/
//取栈顶元素
template<class T>
bool LinkedStack<T>::getTop(T& x)const
{
if(IsEmpty())
return false;
x=top->data;
return true;
}
/*************************************************/
//获取栈长度
template<class T>
int LinkedStack<T>::Length()
{
LinkNode<T>* current=top;
int count=0;
while(current!=NULL)
{
count++;
current=current->link;
}
return count;
}
/*************************************************/
//显示栈元素,先进后出
template<class T>
void LinkedStack<T>::output()
{
LinkNode<T>* current=top;
if(IsEmpty())
{
cout<<"空栈！没有显示的元素!"<<endl;
return;
}
cout<<"链式栈的元素是:"<<endl;
while(current!=NULL)
{
cout<<current->data<<" ";
current=current->link;
}
cout<<endl;
}
/*************************************************/
//逆转栈
template<class T>
void/*LinkedStack<T>* */LinkedStack<T>::Reverse()
{
LinkNode<T>* p=top,*q,*r;
q=p->link;
p->link=NULL;
while(q!=NULL)
{
r=q->link;
q->link=p;
p=q;
q=r;
}
top=p;
}
/**********************************************************
Copyright@2009-2011 by hank(SiChuan University)
***********************************************************/
//Maze.h
#ifndef MAZE_H
#define MAZE_H
#include"Node.h"
#include"ItStack.h"
//迷宫寻找路径
bool pathSearch(int qr,int qc,int Maze[10][10],int Mark[10][10]);
//显示走过的路径
void MarkGet(int Mark[10][10]);
#endif
/**********************************************************
Copyright@2009-2011 by hank(SiChuan University)
***********************************************************/
//Maze.cpp
#include"Maze.h"
#include"ItStack.cpp"
#include<iostream>
using namespace std;
//迷宫寻找路径
bool pathSearch(int qr,int qc,int Maze[10][10],int Mark[10][10])
{
offset move[8]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
char dirN[8][3]={"N","NE","E","SE","S","SW","W","NW"};
int m=10,
p=10;
Mark[1][0]=1;
LinkedStack<item> st;
item it;
it.x=1;it.y=0;it.dir=0;
st.push(it);
int i,j,g,h,d;
while(!st.IsEmpty()/*==false*/)
{
st.pop(it);
i=it.x; j=it.y; d=it.dir;
while(d<8)
{
g=i+move[d].a;
h=j+move[d].b;
if(g==qr && h==qc)
{
it.x=/*g*/i;it.y=/*h*/j;it.dir=d;
st.push(it);
it.x=g;it.y=h;it.dir=4;//出口点的dir默认为0
Mark[g][h]=1;
st.push(it);
st.Reverse();
cout<<"恭喜,成功到达出口!"<<endl;
//cout<<"栈长"<<st.Length()<<endl;
//cout<<"出口是: ("<<g<<","<<h<<")"<<endl;
/*******************************************/
//这一段其实不是很好，只是为了显示才将top设为public,实际上违反了隐蔽性原则
LinkNode<item>* current=st.topPointer();
int k=0;
cout<<"**************唯一路径为**************"<<endl;
while(current!=NULL)
{
int od=current->data.dir;
cout<<"("<<current->data.x<<","<<current->data.y<<","<<dirN[od]<<")"<<" ";
k++;
if((k%3==0))
cout<<endl;
current=current->link;
}
cout<<"/n************迷宫路径探索图************"<<endl;
/**********************************************/
MarkGet(Mark);
return true;
}
else if(Maze[g][h]==0 && Mark[g][h]==0)
{
Mark[g][h]=1;
it.x=i; it.y=j;it.dir=d;
st.push(it);
i=g; j=h; d=0;
}
else
d++;
}
}
cout<<"没有到达出口的路径!"<<endl;
return false;
}
/*************************************************/
//显示走过的路径
void MarkGet(int Mark[10][10])
{
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
cout<<Mark[i][j];
cout<<endl;
}
}
/**********************************************************
Copyright@2009-2011 by hank(SiChuan University)
***********************************************************/
//main.cpp
#include"Maze.h"
#include<iostream>
using namespace std;
int main()
{
//offset move[8]={{-1,0},{-1,1},{0,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int m=10,
p=10;
int Mark[10][10];
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
Mark[i][j]=0;
int Maze[10][10]={{1,1,1,1,1,1,1,1,1,1},
{0,0,0,1,1,0,1,1,0,1},{1,1,1,0,0,1,1,0,1,1},{1,1,0,1,1,0,0,1,1,1},
{1,0,1,1,0,1,1,0,1,1},{1,1,0,1,1,1,1,1,0,1},{1,0,1,1,0,1,1,1,1,1},
{1,0,1,0,1,1,1,1,1,1},{1,1,0,1,0,0,0,1,1,1},{1,1,1,1,1,1,1,0,1,1}};
cout<<"***************迷宫阵型图**************"<<endl;
for(int ii=0;ii<10;ii++)
{
for(int jj=0;jj<10;jj++)
cout<<Maze[ii][jj]<<" ";
cout<<endl;
}
int qr=9,
qc=7;
bool out=pathSearch(qr,qc,Maze,Mark);
return 0;
}
附结果图如下：