// maze.cpp : 定義控制臺應(yīng)用程序的入口點。
//

#include "stdafx.h"
#include<iostream>
using namespace std;

//迷宮算法
//用數(shù)組構(gòu)造迷宮(0表示是障礙，1表示可以通過）

#define INIT_SIZE 6
#define INCREMENT 3

class point
{
public:
	int x;
	int y;
};

//棧定義
typedef struct{
	point* top;
	point* base;
	int size;
}stack;

//初始化棧
bool InitStack(stack &s)
{
	s.base = (point*)malloc(INIT_SIZE*sizeof(point));
	if(!s.base)
		return false;
	s.top = s.base;
	s.size = INIT_SIZE;
	return true;
}
//入棧操作
bool Push(stack &s, point e)
{
	//追加棧空間
	if(s.top - s.base >= s.size)
	{
		s.base = (point*)realloc(s.base, (s.size + INCREMENT)*sizeof(point));
		if(!s.base)
			return false;
		s.top = s.base +s.size;
		s.size += INCREMENT;
	}
	*s.top++ = e;
	return true;

}
//出棧操作
bool Pop(stack &s, point &e)
{
	if(s.top == s.base)
		return false;
	e = *--s.top;
	return true;
}
//獲得棧頂元素
bool GetTop(stack &s, point &e)
{
	if(s.top == s.base)
		return false;
	e = *(s.top-1);
	return true;

}

void CreateMaze(int maze[10][10])
{
	maze[0][0] = 0;maze[0][1] = 0;maze[0][2] = 0;maze[0][3] = 0;maze[0][4] = 0;maze[0][5] = 0;maze[0][6] = 0;maze[0][7] = 0;maze[0][8] = 0;maze[0][9] = 0;
	maze[1][0] = 0;maze[1][1] = 1;maze[1][2] = 1;maze[1][3] = 0;maze[1][4] = 1;maze[1][5] = 1;maze[1][6] = 1;maze[1][7] = 0;maze[1][8] = 1;maze[1][9] = 0;
	maze[2][0] = 0;maze[2][1] = 1;maze[2][2] = 1;maze[2][3] = 0;maze[2][4] = 1;maze[2][5] = 1;maze[2][6] = 1;maze[2][7] = 0;maze[2][8] = 1;maze[2][9] = 0;
	maze[3][0] = 0;maze[3][1] = 1;maze[3][2] = 1;maze[3][3] = 1;maze[3][4] = 1;maze[3][5] = 0;maze[3][6] = 0;maze[3][7] = 1;maze[3][8] = 1;maze[3][9] = 0;
	maze[4][0] = 0;maze[4][1] = 1;maze[4][2] = 0;maze[4][3] = 0;maze[4][4] = 0;maze[4][5] = 1;maze[4][6] = 1;maze[4][7] = 1;maze[4][8] = 1;maze[4][9] = 0;
	maze[5][0] = 0;maze[5][1] = 1;maze[5][2] = 1;maze[5][3] = 1;maze[5][4] = 0;maze[5][5] = 1;maze[5][6] = 1;maze[5][7] = 1;maze[5][8] = 1;maze[5][9] = 0;
    maze[6][0] = 0;maze[6][1] = 1;maze[6][2] = 0;maze[6][3] = 1;maze[6][4] = 1;maze[6][5] = 1;maze[6][6] = 0;maze[6][7] = 1;maze[6][8] = 1;maze[6][9] = 0;
    maze[7][0] = 0;maze[7][1] = 1;maze[7][2] = 0;maze[7][3] = 0;maze[7][4] = 0;maze[7][5] = 1;maze[7][6] = 0;maze[7][7] = 0;maze[7][8] = 1;maze[7][9] = 0;
	maze[8][0] = 0;maze[8][1] = 0;maze[8][2] = 1;maze[8][3] = 1;maze[8][4] = 1;maze[8][5] = 1;maze[8][6] = 1;maze[8][7] = 1;maze[8][8] = 1;maze[8][9] = 0;
	maze[9][0] = 0;maze[9][1] = 0;maze[9][2] = 0;maze[9][3] = 0;maze[9][4] = 0;maze[9][5] = 0;maze[9][6] = 0;maze[9][7] = 0;maze[9][8] = 0;maze[9][9] = 0;
	
}
//基本思想是在確定某點所在位置可行時，先朝該點的左移動一格作為新點，若行則把新點當(dāng)成確定點，并且將新點入棧，若不行則按順時針方向依次移動。
//若各個方向都不行，則讓判斷是否讓棧頂元素出棧。把以經(jīng)過的點都做標(biāo)記。若到達(dá)終點點，則成功，若棧為空，則無出口
void MazePath(int maze[10][10], point startPoint, point endPoint)
{
	stack s;
	InitStack(s);
	int x = startPoint.x;
	int y = startPoint.y;
	maze[x][y] = 2;
	Push(s,startPoint);
	point temp;
	while(x != endPoint.x || y != endPoint.y)
	{
		if(maze[x][y+1] == 1)
		{
			y = y +1;
			// 做標(biāo)記
			maze[x][y] = 2;
			temp.x = x;
			temp.y = y;
			Push(s, temp);
		}
		else if(maze[x+1][y] == 1)
		{
			x = x +1;
			maze[x][y] = 2;
			temp.x = x;
			temp.y = y;
			Push(s, temp);
		}
		else if(maze[x][y-1] == 1)
		{			
			y = y -1;
			maze[x][y] = 2;
			temp.x = x;
			temp.y = y;
			Push(s, temp);

		}
		else if(maze[x-1][y] == 1)
		{
			x = x -1;
			maze[x][y] = 2;
			temp.x = x;
			temp.y = y;
			Push(s, temp);

		}
		else
		{
			// 若該點四周都不通，則判斷棧頂元素。
			if(GetTop(s, temp))
			{
				x = temp.x;
				y = temp.y;
			    //若棧頂元素四周也不通則將棧頂元素出棧并且考察下前一個可行元素
				if( maze[x][y+1] != 1 && maze[x+1][y] != 1 && maze[x][y-1] != 1 && maze[x-1][y] != 1)
				{
					Pop(s, temp);
					if(GetTop(s, temp))
			        {
						 x = temp.x;
						 y = temp.y;
					}
					else
					{
						cout << "無出口！！！！" <<endl;
				        return;

					}


				}
			}
			else
			{
				cout << "無出口！！！！" <<endl;
				return;
			}

		}
	}
	// 倒過來顯示路徑
	stack t;
	InitStack(t);
	while(Pop(s, temp))
	{
		Push(t,temp);
	}
	int i = 1;
	cout << "路徑是：" << endl;
	while(Pop(t, temp))
	{
		cout << "第" << i++ << "步[" << temp.x << "," << temp.y <<"]";
	}
	cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int maze[10][10];
	CreateMaze(maze);
	cout << "迷宮圖形是：" << endl;
	for( int i = 0; i < 10; i++)
	{
		for(int j = 0; j < 10; j++)
			cout << maze[i][j] << " ";
		cout << endl;
	}
	point start;
	start.x =1;
	start.y =1;
	point end;
	end.x =8;
	end.y =8;
	MazePath(maze, start, end);

	return 0;
}