/************************************************************************/
/*自定义栈 */
/*通过自定义的简单栈以满足迷宫求解 */
/*功能：push() 将元素加入栈中 */
/* pop() 退栈；topValue() 获得栈顶元素 */
/* clear() 清除栈 length() 获得栈中元素个数*/
栈的应用之迷宫：maze:
（0）过程：
（0.1）构建迷宫：
（0.2）寻找路径：
（0.3）打印路径：
（1）迷宫图解：
（1.1）迷宫图解：
（1.2）迷宫路径：
寻找一条从入口到出口的路径，路径是一个点栈（即栈中元素是点），每个点上都没有障碍，
且每一个点都是前一个点的上、下、左、右（东、南，西，北）的邻居。
（2）思路：穷举求解：
从入口出发，沿着某一个方向探索，如果可以走通，则继续前行；
否则沿原路返回，换一个方向再继续探索，知道所有的通路都探索到为止。
/************************************************************************/
#include <stack>
#include <iostream>
#include <windows.h>
using namespace std;
template<typename Elem> class PathStack: public stack<Elem>
{
private:
int size;
int top;
Elem* listArray;
public:
PathStack(int sz ){
size = sz;
top = 0;
listArray = new Elem[sz];
}
~PathStack(){ delete []listArray; }
void clear(){ top = 0; }
/****向栈中加入元素****/
bool push(const Elem& item);
/***********退栈**********/
Elem pop();
/********获得栈顶元素*******/
Elem topValue() const;
int length() const { return top; }
bool isEmpty();
};
template<typename Elem>
bool PathStack<Elem>::push(const Elem& item){
if(top == size) return false;
listArray[top++] = item;
return true;
}
template<typename Elem>
bool PathStack<Elem>::isEmpty(){
return top==0;
}
template<typename Elem>
Elem PathStack< Elem>::pop(){
Elem it;
if(top == 0) return it;
it = listArray[--top];
return it;
}
template<typename Elem>
Elem PathStack< Elem>::topValue() const{
Elem it;
if(top == 0) return it;
it = listArray[top - 1];
return it;
}
//迷宫求解的方法类
//功能：通过findPath() 方法实现对路径的查找
// 通过printPath()方法将路径打印出来
class MazeSolveMethod
{
private:
static int maze[10][10];//存放迷宫数据
PathStack<int> pathStack;//定义栈
public:
MazeSolveMethod():pathStack(100){
}
~MazeSolveMethod(){ }
bool findPath(int startX,int startY);
void printPath() const;
};
int MazeSolveMethod::maze[10][10] = {
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,1,1,0,0,0,0,1},
{1,1,0,1,1,0,1,1,0,1},
{1,1,0,0,1,0,1,1,0,1},
{1,0,1,0,1,0,0,1,0,1},
{1,0,1,0,0,0,0,1,0,1},
{1,1,1,1,1,0,0,0,0,1},
{1,1,1,1,1,1,1,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
/*
maze[i][j]=0,表示可通；
maze[i][j]=1,表示不通；
maze[i][j]=2,表示已经走过；
maze[i][j]=3,也表示死胡同；
*/
bool MazeSolveMethod::findPath(int startX,int startY){
int x = startX;
int y = startY;
pathStack.push(x);
pathStack.push(y);
maze[x][y] = 2;
cout<<"进入方法!!"<<endl;
while(!pathStack.isEmpty()){
/*方法不好之处是由于起点通常在左上，然后终点在右下，所以
应该先将判断当前节点的右，下，然后再判断左，上；这样可以快一点；
另外，此中如果无法到达终点，好像是无限循环的。显然不可以。
*/
if(maze[x][y+1] == 0){
/*判断当前节点的右邻居*/
pathStack.push(x);
pathStack.push(++y);
maze[x][y] = 2;
}else if(maze[x+1][y] == 0){
/*判断当前节点的下邻居*/
pathStack.push(++x);
pathStack.push(y);
maze[x][y] = 2;
}else if(maze[x][y-1] == 0){
/*判断当前节点的左邻居*/
pathStack.push(x);
pathStack.push(--y);
maze[x][y] = 2;
}else if(maze[x-1][y] == 0){
/*判断当前节点的上邻居*/
pathStack.push(--x);
pathStack.push(y);
maze[x][y] = 2;
}
if(x==6&& y==6)
return true;
cout<<"( "<<x<<" , "<<y<<" ) ";
/*
注意：此中的当前点的上下左右可通，则将当前点可通的上下左右压入栈中；
然后更新当前点为刚压入栈中的元素。
因为：此中是++x,--x,++y,--y,所以x，y发生了改变，即当前点发生了更新；
*/
if(maze[x-1][y] != 0 && maze[x][y+1] != 0 && maze[x+1][y] != 0 && maze[x][y-1] != 0){
/*如果当前位置的右，下，左，上均走过或不通*/
maze[x][y] = 3;
y = pathStack.pop();
x = pathStack.pop();
/*当前点的上下左右不通，或者已经走过，就将当前点标记为死胡同。
然后从栈中弹出当前点。
*/
if(pathStack.isEmpty()==true)
return false;
y = pathStack.topValue();
int temp = pathStack.pop();
x = pathStack.topValue();
pathStack.push(temp);
/*
更新当前点，先获取y，要获取x，必须弹出y，然后在将弹出的y压入进去。（x始终没有弹出。）
*/
}
}
return false;
}
void MazeSolveMethod::printPath() const{
cout<<"printPath"<<endl;
for(int i=0; i<10; i++){
for(int j=0; j<10; j++){
if(maze[i][j] == 2)
cout<<'>'<<" ";
else if(maze[i][j] == 3)
cout<<'x'<<" ";
else if(maze[i][j]==1)
cout<<1<<" ";
else
cout<<0<<" ";
}
cout<<endl;
}
}
int main(){
MazeSolveMethod solve;
if(solve.findPath(1,1))
solve.printPath();
else
cout<<"no path from start to end "<<endl;
system("pause");
return 0;
}