數據結構應用：利用棧破解迷宮游戲

最近剛開始學數據結構，發現數據結構真是個神奇的東西哈，很多現實中的問題都可以用不同的數據結

構來解決，比如利用和棧中綴表達式編寫一個計算機程序，利用棧破解迷宮游戲，今天我就來跟大家分

享一下如何利用棧來破解迷宮游戲。

學過數據結構的人都知道，棧的特點是：后進先出（First In Last Out）;也就是說只能在棧的尾部進

行壓棧和出棧，而且出棧的時候只能從最后一個數據開始。如下圖：

而我們在破解迷宮游戲的時候采用的方法是“回溯”，也就是在尋找通路的時候，每找到一個通路，就將這個數據壓棧，這樣當前位置的上一個位置就位于棧的頂部，假如當前位置的上下左右都找不到通路的時候，就開始回溯，也就是開始從來的路往回走，而之前走過的路都存在棧里面，所以只需要一個一個的Pop就能依次往回退，每退一次，就尋找上下左右有沒有通路，如果找到通路就繼續往下走，并壓棧，直到走出整個迷宮。大概思路就是這樣啦

首先要如何構建一個迷宮呢，如果手動在程序中輸入的話，比較麻煩而且不夠靈活，所以我們可以先將迷宮寫到一個文件里，然后在程序中去讀文件，這樣就ok辣。如下圖

接下來呢我們就要在文件里面去讀這個迷宮咯，具體的代碼：

void GetMaze(int *a, int n)
{
	FILE* fout = fopen("Maze Map.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 CheckAccess(int *a, int n, pos& next)
{
	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())
	{
		if (cur.row == n - 1)
		{
			return true;
		}
		a[cur.row*n + cur.col] = 2;   //將之前走過的位置保存起來
		pos next = cur;
		next.row--;                   //上路
		if (CheckAccess(a,n,next))
		{
			next=cur;
			path.push(cur);
			continue;
		}
		next.row++;                  //下路
		if (CheckAccess(a, n, next))
		{
			next=cur;
			path.push(cur);
			continue;
		}
		next.col--;                //左路
		if (CheckAccess(a, n, next))
		{
			next= cur;
			path.push(cur);
			continue;
		}
		next.col++;                //右路
		if (CheckAccess(a, n, next))
		{
			next = cur;
			path.push(cur);
			continue;
		}
           cur = path.top();
	       path.pop();
       }
	return false;
	}
	

下面我們可以將迷宮打印出來了：

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;
	}
	cout << endl;
}

以上便是棧破解迷宮的方法，其實這個代碼寫的并不好，還有很多許多地方需要改進和優化，比如如何找到最短路徑等，希望讀者們能積極為我指出來，一起相互學習，共同進步。