大家都知道，至于迷宮的求解問題，可以用窮舉法進(jìn)行求解。那么什么是窮舉法了，就是將每一種可能的情況都窮舉完。而具體到迷宮的求解問題上，由于在求解過程中可能會遇到某一路徑不可行的情況，此時我們就必須按原路返回，這時自然也就會想到棧的應(yīng)用了，因?yàn)闂５囊粋€很重要的特性就是”先進(jìn)后出”，可以用來記錄每次所探索的路徑，方便在原路返回的過程中，得到上一步所走路徑，再按此方法，退回到可以走得通的位置上，繼續(xù)探索下去，直到到達(dá)終點(diǎn)或者最終無法到達(dá)，正常退出程序?yàn)橹埂?/p>

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：申請域名、虛擬主機(jī)、營銷軟件、網(wǎng)站建設(shè)、烏魯木齊網(wǎng)站維護(hù)、網(wǎng)站推廣。

      下面我們就一起來探索迷宮?。。?/p>

   首先是得到迷宮地圖，這里我們用文件流來實(shí)現(xiàn)。

void GetMaze(int *a, size_t n)
{
	FILE* fout = fopen("MazeMap.txt", "r");  //打開迷宮地圖
	assert(fout);
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = 0; j < n;)
		{
			char ch = fgetc(fout);  //讀取一個字符
			if (ch == '0' || ch == '1')
			{
				a[i*n + j] = ch - '0';
				j++;
			}
			else
			{
				continue;
			}
		}
	}
	fclose(fout);
}

給出迷宮地圖：

0為通路，1為墻

  然后我們將迷宮打印出來

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

 接著定義位置結(jié)構(gòu)體，用此結(jié)構(gòu)體表示當(dāng)前位置的橫縱坐標(biāo)

struct Pos
{
	int _row;
	int _col;
};

 然后再從給定的入口位置開始對此位置的上下左右四個相鄰位置進(jìn)行判斷，若為1則行不通，若為0，則可以走，，并將此位置進(jìn)行壓棧。將走過的位置改為2，以備在回退的時候可以用

bool MazePath(int* a, size_t n, Pos& entry, stack& path)
{
	Pos cur = entry;
	path.push(cur);    //當(dāng)前位置壓棧
	while (!path.empty())
	{
		a[cur._row *n + cur._col] = 2;   //走過的位置標(biāo)記為2
		Pos next = cur; //將當(dāng)前位置進(jìn)行標(biāo)記
		//上
		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._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;
		}
		 //上下左右都走不通，回退
		cur = path.top();  
		path.pop();
		if (cur._row == n - 1)   // 出口
		{
			return true;
		}
	}
	return false;
}

判斷當(dāng)前位置的下一步是否走得通

bool CheckIsAccess(int* a, size_t n, Pos next)
{
	assert(a);
	if ((next._col >= 0) && (next._col < n) && (next._row >= 0) && (next._row < n) &&
		(a[next._row *n + next._col] == 0))
	{
		return true;
	}
	else
		return false;
}

這樣一個簡單的迷宮就完成了，是不是看起來挺容易的呢？如果有不懂得地方，歡迎留言。有高見也歡迎留言~