迷宮問題，是棧的一個經(jīng)典應用。在今多年的面試題中特別常見。本博主呢，也就研究了一二。

成都創(chuàng)新互聯(lián)是一家從事企業(yè)網(wǎng)站建設、成都做網(wǎng)站、成都網(wǎng)站制作、行業(yè)門戶網(wǎng)站建設、網(wǎng)頁設計制作的專業(yè)網(wǎng)絡公司，擁有經(jīng)驗豐富的網(wǎng)站建設工程師和網(wǎng)頁設計人員，具備各種規(guī)模與類型網(wǎng)站建設的實力，在網(wǎng)站建設領(lǐng)域樹立了自己獨特的設計風格。自公司成立以來曾獨立設計制作的站點上千多家。

若有一迷宮，如何尋找通路？

解題思路：

   迷宮，可將其看成一個二維數(shù)組。給定一個入口，需要判斷此入口的上下左右是否越界，是否有通路點。若有通路點，將此點前一個通路點記錄并將其置為非0（防止訪問下一個通路點時再次判斷）。繼續(xù)尋找下一個通路,...以此類推。若查找不到通路點，則需要回溯。判斷是否還有其他通路。

回溯呢，就是將從記錄的通路點回退。此特征呢，和我們的棧很相似。所以，棧就在此處派上用場嘍。

  那么如何判斷迷宮是否有通路呢？

  判斷條件：（1）有通路。當行或者列到達邊界時即可判斷。

            （2）無通路。當回溯時，需要從棧中取出元素。當棧為空時即可判斷。

假設有如下迷宮。（迷宮中0為通路）入口點（2,0）。

分析：

  看到此迷宮，可將其看成二維數(shù)組。但是在程序中不可能一個一個輸入（若迷宮很大呢）。所以可將其以文件的形式讀取。我們看到在此迷宮處，有一個通路點處有兩條通路，若先走下面，行到達邊界處，則可直接得出有通路。若先右方，最終無通路可走，則需要回溯，在進一步的判斷。當回溯到岔路口時，發(fā)現(xiàn)下方還有路可走。繼續(xù)向下走，最終行到達邊界處，即有通路。

程序?qū)崿F(xiàn)：

"Maze.h"

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
#include <stack>
#define N 10
using namespace std;

struct Pos
{
	int _row;//行
	int _col;//列
};

//從文件中讀出數(shù)據(jù)，并以一位數(shù)組存放
void GetMaze(int *a,int n) 
{
	FILE* f = fopen("test.txt","r");
	assert(f);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;)
		{
			char ch = fgetc(f);
			if(ch == '0' || ch == '1')
			{
				a[i*n+j] = ch - '0';
				j++;
			}
			else
			{
				continue;
			}
		}
	}
}

//打印迷宮
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;
	}
}
//是否有通路
bool PathIsAccess(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;
	}
	return false;
}

bool  MazePath(int *a,int n,Pos& entry,stack<Pos>& path)
{
	 Pos cur = entry;
	 path.push(cur);
	 while(!path.empty())
	 { 
		 a[cur._row*n+cur._col] = 2;//壓棧后將其置為2，防止再次訪問到
		 if((cur._col == n-1)||(cur._row == n-1))//通路條件，行或列到達邊界
		 {
			 return true;
		 }
		 //上
		 Pos next = cur; //將上一個通路點保存
		 next._row--;
		 if(PathIsAccess(a,n,next))//是否越界
		 {
			 cur = next;
			 path.push(cur);
			 continue;
		 } 
		  //左
		 next = cur;
		 next._col--;
		 if(PathIsAccess(a,n,next))
		 {
			 cur = next;
			 path.push(cur);
			 continue;
		 } 
		 //右
		 next = cur;
		 next._col++;
		 if(PathIsAccess(a,n,next))
		 {
			 cur = next;
			 path.push(cur);
			 continue;
		 }
		 //下
		 next = cur;
		 next._row++;
		 if(PathIsAccess(a,n,next))
		 {
			 cur = next;
			 path.push(cur);
			 continue;
		 }
		 cur = path.top();//回溯
		 path.pop();
	 }
	return false;
}
void Test()
{
	int a[N][N] = {};
	GetMaze((int *)a,N);
	PrintMaze((int *)a,N);

	stack<Pos> path;
	Pos entry = {2,0};
	bool ret = MazePath((int *)a,N,entry,path);

	cout<<"是否有通路"<<ret<<endl;
	PrintMaze((int *)a,N);

}

測試結(jié)果：

（1）先走右方（出現(xiàn)回溯）

（2）先走下方

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調(diào)度，確保服務器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務器買多久送多久。

網(wǎng)站欄目：棧---解決迷宮問題-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://aaarwkj.com/article32/iedpc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供云服務器、網(wǎng)站策劃、搜索引擎優(yōu)化、建站公司、定制開發(fā)、品牌網(wǎng)站設計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)