應(yīng)用棧求解迷宮問題（C++實現(xiàn)）

棧是數(shù)據(jù)結(jié)構(gòu)中一種重要的線性結(jié)構(gòu)，限定僅在表尾進(jìn)行插入和刪除操作的線性表，因此我們也可以認(rèn)為它是一種特殊的線性表。由于棧的這個特點，我們又可以稱其為后進(jìn)先出的結(jié)構(gòu)。如圖所示：

       由于棧具有后進(jìn)先出的性質(zhì)我們可以利用，是程序設(shè)計中一個有用的工具。利用棧我們可以來實現(xiàn)數(shù)制轉(zhuǎn)換、后綴表達(dá)式求值、迷宮求解等等。在書本上我們可以看到用C語言實現(xiàn)的簡單思路，但是程序仍舊存在許多bug。今天，我想嘗試用強(qiáng)大的C++來實現(xiàn)。

      迷宮問題的求解思路大致則是從入口出發(fā)，順著某一方向向前探索，若能走通，則繼續(xù)向前探索；若不能走通，則換一方向進(jìn)行探索，直至所有可能的通路都探索完為止。利用棧的特性，我們可以將探索過可通的路依次進(jìn)棧，如果遇到不通的路則進(jìn)行出棧操作，進(jìn)行回退，重復(fù)探索。

       ps：為了方便起見我利用了一個記事本來存放迷宮，用1表示不通，0表示通路。將走過的路程標(biāo)注為2.

代碼實現(xiàn)：

struct Pos	 //可通過下標(biāo)訪問位置
{
	int _ROW;
	int _COL;
};

void GetMaze(int *a,int n)	//從文件中讀出迷宮地圖
{
	FILE* fout=fopen("Maze.txt","r");
	assert(fout);
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; 
			)
		{
			char ch=fgetc(fout);
			if(ch=='0' || ch=='1')
			{
				a[i*n+j]=ch-'0';
				++j;
			}
			else
			{
				   continue;
			}
		}
	}
	fclose(fout);
}

bool CheckIsAccess(int *a,int n,Pos next)//檢查是否為通路
{
	assert(a);
	if( (next._ROW>=0) && (next._ROW<n) && (next._COL>=0) && (next._COL<n) && (a[next._ROW*n+next._COL]==0))
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool MazePath(int *a,int n,Pos& entry,stack<Pos>& path)	   //探索過程
{
	Pos cur=entry;
	path.push(cur);
	while(!path.empty())
	{
		Pos next=cur;
		a[cur._ROW*n+cur._COL]=2;
		
		if(next._ROW==n-1) /*|| next._ROW==0 || next._COL==n-1 ||  next._COL==0*/
		{
			return true;
		}
		//判斷上下左右是否為通路 
		next=cur;
		next._ROW--;// 上
		if(CheckIsAccess(a,n,next))
		{	
			cur=next;
			path.push(cur);
			continue;
		}
		next=cur;
		next._ROW++;//下
		if(CheckIsAccess(a,n,next))
		{
			cur=next;
			path.push(cur);
			continue;
		}
		next=cur;
		next._COL--;//左
		if(CheckIsAccess(a,n,next))
		{
			cur=next;
			path.push(cur);
			continue;
		}
		next=cur;
		next._COL++;//右
		if(CheckIsAccess(a,n,next))
		{
			cur=next;
			path.push(cur);
			continue;
		}
		//回退
		cur=path.top();
		path.pop();
		
	}					   
}



void PrintMaze(int *a,int n)   //輸出迷宮
{
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
		    cout<<a[i*n+j]<<" ";
		}
		cout<<endl;
	}	
}