#include<iostream>
#include<stdlib.h>
#include<iomanip>
#include<string>
using namespace std;

struct PosType{ //平面上点的结构
	int x;
	int y;
}; //coordinates

bool PEqual(struct PosType A, struct PosType B)
{
	if(A.x == B.x  && A.y == B.y )
		return true;
	else
		return false;
}

struct PosType MakePost(int a, int b)
{
	struct PosType A;
	A.x = a;
	A.y = b;
	return A;
}

struct PosType NextPost(struct PosType A, int i)
{
	struct PosType B;
	switch(i){
	case 1:
		B.x = A.x + 1;
		B.y = A.y;
		break;
	case 2:
		B.x = A.x + 1;
		B.y = A.y + 1;
		break;
	case 3:
		B.x = A.x + 1;
		B.y = A.y - 1;
		break;
	case 4:
		B.x = A.x;
		B.y = A.y + 1;
		break;
	case 5:
		B.x = A.x - 1;
		B.y = A.y + 1;
		break;
	case 6:
		B.x = A.x - 1;
		B.y = A.y;
		break;
	case 7:
		B.x = A.x;
		B.y = A.y - 1;
		break;
	case 8:
		B.x = A.x - 1;
		B.y = A.y - 1;
		break;
	default:
		cout << "错误方向." << endl;
        break;
	}
	return B;
}

struct SElemType{  //栈中元素的结构
	int ord;                 //通道块在路径上的序号
	struct PosType seat;  //通道块在迷宫中的坐标位置
	int di;      //从此通道块走向下一通道块的方向
};

struct SElemType MakeSET(int a, struct PosType B, int c)
{
	struct SElemType D;
	D.ord = a;
	D.seat = MakePost(B.x, B.y);
	D.di = c;
	return D;
}

void Exception(bool Condition, string ErrorMsg){
	if(Condition){cerr << ErrorMsg << endl; abort();}
}

static const int InitStackSize = 10;

template<class ElemType>
class Stack{
	public:
		Stack();  //构造函数
		~Stack(){ delete []Array;}  //析构函数
		bool IsEmpty() const {return top == -1;}  //判栈空
		bool IsFull() const {return top == MaxSize - 1;}   //判栈满
		void MakeEmpty() {top = -1;}     //将栈清空
		void Push( ElemType &x);  //进栈
		void Pop();        //出栈
		const ElemType &Top(); //取顶点元素
		const Stack &operator=(const Stack &R);
		void PrintMazeRoute();
	private:
		ElemType *Array;     //存放结点的数组名
		int top;             //栈顶指针
		int MaxSize;         //栈的容量
		void DoubleArray(int Max);  //更新数组的容量
};

template<class ElemType>
Stack<ElemType>::Stack():top(-1),MaxSize(InitStackSize){
	        //构造函数，空间大小为MaxSize
	Array = new ElemType[MaxSize];
}

template<class ElemType>
const ElemType &Stack<ElemType>::Top(){ //读取栈顶结点
	Exception(IsEmpty(), "Underflow:Stack is empty!");
	return Array[top];
}

template<class ElemType>
void Stack<ElemType>::Push( ElemType &x){
	if(top + 1 == MaxSize) DoubleArray(2*MaxSize);
	Array[++top] = x;  //新结点放入新的栈顶位置
}

template<class ElemType>
void Stack<ElemType>::Pop(){  //将栈顶元素出栈
	Exception(IsEmpty(), "Stack is underflow!");
	top--;
}

template<class ElemType>
const Stack<ElemType> &Stack<ElemType>::operator=(const Stack<ElemType> &R){
	if(this == &R) return *this;
	delete []Array;
	Array = new ElemType[R.MaxSize];  //分配存储单元 
		top = R.top;
	for(int j=0; j<=top; j++)Array[j] = R.Array[j]; //逐个复制结点
	return *this;
}

template<class ElemType>
void Stack<ElemType>::DoubleArray(int Max){
	ElemType *oldarr = Array;
	Exception((MaxSize >= Max), "New size is too small!");
	Array = new ElemType[Max];
	for(int k=0; k<=top; k++)
		Array[k] = oldarr[k];  //逐个复制结点
	MaxSize = Max;
	delete []oldarr;
	return;
}

template<class ElemType>
void Stack<ElemType>::PrintMazeRoute()//输出一条通路的二元组(i,j)数据序列
{
	ElemType e;
	e = Top();
	Pop();
	if(!IsEmpty())
		PrintMazeRoute();
	cout << "->(" << e.seat.x << ',' << e.seat.y << ')';
}

bool MazePath(int maze[14][17], PosType start, PosType end)
{                                  //求从start到end的一条通道
	Stack<SElemType> S;
	SElemType e;
//	InitStack(S);
	PosType curpos = {start.x, start.y};        //设定当前位置为入口位置
	int curstep = 1;        //第一步
	do{
		if(maze[curpos.x][curpos.y] == 0){
			maze[curpos.x][curpos.y] = 8;  //留下足迹
			e = MakeSET(curstep, curpos, 1);   //赋值
			S.Push(e);        //加入路径
			if(PEqual(curpos, end)){ //到达终点
				cout << "一条通路的二元组数据序列:" << endl;
				S.PrintMazeRoute();
				cout << endl;
				return true;  
			}
			curpos = NextPost(curpos, 1); //下一位置是当前位置的东邻
			curstep++;       //探索下一步
		}else{        //当前位置不能通过
			if(!S.IsEmpty()){
				e = S.Top();
				S.Pop();
				while(e.di == 8 && !S.IsEmpty()){
					maze[(e.seat).x][(e.seat).y]=3;   //留下不能通过的记号
					e = S.Top();
					S.Pop();      //退回一步
				}
				if(e.di < 8){
					e.di++;         //换下一个方向探索
					S.Push(e);
					curpos = NextPost(e.seat, e.di);   //设定当前位置是该新方向上的相邻块
				}
			}
		}
	}while(!S.IsEmpty());
	return false;
}

int main()
{
	int A[14][17]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//迷宫（包括围墙）的对应矩阵：
	{1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
	{1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
	{1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
	{1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},
	{1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
	{1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
	{1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
	{1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,0,1},
	{1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1},	
	{1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},	
	{1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
	cout << "迷宫是:(1 表示障碍，0表示可以通过)" << endl;
	for( int i = 0; i < 14;  i++ ){
        for(int j = 0; j < 17; j++)
			cout << setw(3) << A[i][j];
		cout << endl;
	}
	PosType B = {1, 1};
	PosType C = {12, 15};
	if (MazePath(A, B, C)){
		cout <<"路径是沿着 8 走" << endl;
        for(int k = 0; k < 14; k++){
            for(int l = 0; l < 17; l++)
			    cout << setw(3) << A[k][l];
		        cout << endl;
		}
	}
	else cout << "通不过." << endl;
	return 0;
}