怎么找到一個迷宮的出口呢。首先要知道迷宮長啥樣，之后知道出入口，再之后就是找通路的過程了。

創(chuàng)新互聯(lián)服務(wù)項目包括昭通網(wǎng)站建設(shè)、昭通網(wǎng)站制作、昭通網(wǎng)頁制作以及昭通網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，昭通網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到昭通省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

    顯然主要的部分是如何找通路。我們就舉一個例子：

    在這個迷宮中0就是墻，1就是路。那么我們可以用一個二維數(shù)組來表示這個迷宮。之后我們需要一種結(jié)構(gòu)來實現(xiàn)我們表示位置的移動。

struct Pos
{
	size_t line;
	size_t row;
};

    這個結(jié)構(gòu)體通過記錄行和列來表示現(xiàn)在處在迷宮的哪個位置。

    現(xiàn)在就可以開始進行找通路的過程了。我們很容易想到通過試探當(dāng)前位置的周圍四個或三個位置來找到下一個應(yīng)該去的位置，直到走到出口就算任務(wù)完成了。但是我們在試探的過程中，走到了下個位置，一定要把之前的位置做一個標(biāo)記，否則我們的程序會一直在兩個位置之間走來走去。我們這里通過把之前的位置置為2來防止它走來走去。

                if (pos.row>0 && maze[pos.line * 10 + pos.row - 1] == 1)//左
		{
			p.push(pos.line * 10 + pos.row);
			pos.row--;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.row < 9 && maze[pos.line * 10 + pos.row + 1] == 1)//右
		{
			p.push(pos.line * 10 + pos.row);
			pos.row++;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.line > 0 && maze[(pos.line - 1) * 10 + pos.row] == 1)//上
		{
			p.push(pos.line * 10 + pos.row);
			pos.line--;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.line < 9 && maze[(pos.line + 1) * 10 + pos.row] == 1)//下
		{
			p.push(pos.line * 10 + pos.row);
			pos.line++;
			maze[(pos.line * 10 + pos.row)] = 2;
		}

    這段代碼就是對上下左右四個方向進行試探的過程，其中我們用一個棧記錄下了我們走過的位置，因為迷宮里面有岔路，所以我們走錯時需要進行回溯。而選用棧是因為棧的后進先出的特性。說到走進岔路進行回溯，當(dāng)我們發(fā)現(xiàn)上面四種試探完成卻沒有通路時，就是我們已經(jīng)走到了死胡同的最深處，需要進行回溯了，那末回溯的過程就是進行拿取棧頂元素，之后出棧的過程。

                        maze[(pos.line * 10 + pos.row)] = 3;
			pos.line = p.top() / 10;
			pos.row = p.top() - pos.line*10;
			p.pop();

    上面的代碼就是進行回溯的過程，再加一個是否到達(dá)終點的判斷就完成了主要部分。

                if (pos.line * 10 + pos.row == 91)
		{
			PrintMaze(maze);
			return 1;
		}

    上面就是找路徑的過程，也就是我們代碼的主要邏輯部分。剩下的就是一些注意事項。

    讀迷宮圖我是通過文件指針，fopen，fgets，fclose來實現(xiàn)的。之后在創(chuàng)建了一個二維數(shù)組之后我們給函數(shù)傳參的時候需要把它轉(zhuǎn)換成一個一級指針來傳遞。我們操作就把它當(dāng)作一個一維數(shù)組來處理。因為在內(nèi)存中一維數(shù)組和二維數(shù)組是一樣的，只不過表示方式不一樣而已，我們這個迷宮通過二維數(shù)組表示比較直觀，但是用一維數(shù)組一樣可以處理。

    下面是完整的代碼和運行的結(jié)果。

結(jié)果：

    可以看到上面的是最初的迷宮，經(jīng)過我們走迷宮的過程，將走過的岔路標(biāo)記為了3，正確的通路標(biāo)記為了2。

    完整代碼：

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<assert.h>
#include<stack>
using namespace std;

struct Pos
{
	size_t line;
	size_t row;
};

void InitMaze(int *maze)
{
	FILE *p = fopen("maze.txt", "r");
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10;)
		{
			int tmp =(int)(fgetc(p))-'0';
			if (tmp == 0)
				maze[i*10+j] = 0;

			if (tmp == 1)
				maze[i*10+j] = 1;

			if (tmp == 1 || tmp == 0)
				j++;
		}
	}

	fclose(p);
}

void PrintMaze(int *maze)
{
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			cout << maze[i * 10 + j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

int GoMaze(int *maze,Pos start)
{
	assert(maze);
	stack<int> p;
	
	Pos pos;
	pos.line = start.line;
	pos.row = start.row;

	while (1)
	{
		maze[(pos.line * 10 + pos.row)] = 2;

		if (pos.row>0 && maze[pos.line * 10 + pos.row - 1] == 1)//左
		{
			p.push(pos.line * 10 + pos.row);
			pos.row--;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.row < 9 && maze[pos.line * 10 + pos.row + 1] == 1)//右
		{
			p.push(pos.line * 10 + pos.row);
			pos.row++;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.line > 0 && maze[(pos.line - 1) * 10 + pos.row] == 1)//上
		{
			p.push(pos.line * 10 + pos.row);
			pos.line--;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.line < 9 && maze[(pos.line + 1) * 10 + pos.row] == 1)//下
		{
			p.push(pos.line * 10 + pos.row);
			pos.line++;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else
		{
			maze[(pos.line * 10 + pos.row)] = 3;
			pos.line = p.top() / 10;
			pos.row = p.top() - pos.line*10;
			p.pop();
		}

		if (pos.line * 10 + pos.row == 91)
		{
			PrintMaze(maze);
			return 1;
		}
	}	
}

void Mazetest()
{
	int maze[10][10];
	Pos p;
	p.line = 2;
	p.row = 0;
	InitMaze((int *)maze);
	PrintMaze((int *)maze);
	GoMaze((int *)maze,p);
}

int main()
{
	Mazetest();
	return 0;
}

網(wǎng)站題目：以棧解決迷宮問題
文章鏈接：http://jinyejixie.com/article10/ijgpdo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、虛擬主機、商城網(wǎng)站、小程序開發(fā)、動態(tài)網(wǎng)站、Google

廣告

聲明：本網(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)