真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

以棧解決迷宮問題

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

創(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)在就可以開始進行找通路的過程了。我們很容易想到通過試探當前位置的周圍四個或三個位置來找到下一個應(yīng)該去的位置,直到走到出口就算任務(wù)完成了。但是我們在試探的過程中,走到了下個位置,一定要把之前的位置做一個標記,否則我們的程序會一直在兩個位置之間走來走去。我們這里通過把之前的位置置為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;
		}

    這段代碼就是對上下左右四個方向進行試探的過程,其中我們用一個棧記錄下了我們走過的位置,因為迷宮里面有岔路,所以我們走錯時需要進行回溯。而選用棧是因為棧的后進先出的特性。說到走進岔路進行回溯,當我們發(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();

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

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

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

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

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

結(jié)果:

以棧解決迷宮問題

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

    完整代碼:

#define _CRT_SECURE_NO_WARNINGS 1

#include
#include
#include
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 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;
}

本文題目:以棧解決迷宮問題
本文鏈接:http://weahome.cn/article/ijgpdo.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220(工作日)

18980820575(7×24)

提交需求

返回頂部