我們知道棧的特點(diǎn)是：后進(jìn)先出（First In Last Out）;也就是說只能在棧的尾部進(jìn)

為阿克蘇等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及阿克蘇網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、阿克蘇網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

行壓棧和出棧，而且出棧的時(shí)候只能從最后一個(gè)數(shù)據(jù)開始。

  所以我們利用棧這個(gè)特點(diǎn)，來實(shí)現(xiàn)這個(gè)迷宮。在這之中我們要采用“回溯”的方法去處理當(dāng)遇到路徑不通的情況。

  原理：每找到一個(gè)通路，就將這個(gè)數(shù)據(jù)壓棧，這樣當(dāng)前位置的上一個(gè)位置就位于棧的頂部，假如當(dāng)前位置的上下左右都找不到通路的時(shí)候，就開始回溯，也就是開始從來的路往回走，而之前走過的路都存在棧里面，所以只需要一個(gè)一個(gè)的Pop就能依次往回退，每退一次，就尋找上下左右有沒有通路，如果找到通路就繼續(xù)往下走，并壓棧，直到走出整個(gè)迷宮。

#define _CRT_SECURE_NO_WARNINGS 1
#include"MazeMap.h"
#include<stdio.h> 


void test()
{
	int a[N][N];
	GetMaze((int*)a, N);
	stack<pos> paths;
	pos entry = { 2, 0 };
	cout << searchpath((int*)a, 10, entry, paths)<<endl;
	display((int*)a, N);
}
int main()
{
	test();
	system("pause");
	return 0;
}

#pragma once
#include<stack>
#include<assert.h>

#define N  10
#include<iostream>
using namespace std;

struct pos
{
	int _row;
	int _col;
};
void GetMaze(int* a, int n)     
{
	assert(a);
	FILE* fout = fopen("C:\\maze.txt", "r");
	assert(fout);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n;)
		{
			char ch = fgetc(fout);
			if (ch == '1' || ch == '0') //只讀有效的字符，遇空格不轉(zhuǎn)換
			{
				a[i * n + j] = ch - '0';
				j++;
			}
			else
			{
				continue;
			}
		}
	}
	fclose(fout);
}
bool CheckisAccess(int *a, int n, const pos& next)//檢查當(dāng)前的路徑是否通行
{
	int row = next._row;
	int col = next._col;
	if (row >= 0 && row < n&&col >= 0 && col < n&&a[next._row*n + next._col] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
bool searchpath(int* a, int n, pos entry, stack<pos>& paths)
{
	assert(a);
	paths.push(entry);     //將入口地址（坐標(biāo)）push到棧中
	while (!paths.empty())  //如果棧為空，就沒找到出口
	{
		pos cur = paths.top();     
		a[cur._row*n + cur._col] = 2;  //將走過的路徑置為2
		if (cur._row == n - 1)
		{
			return true;
		}
		pos next = cur;     //先將cur賦給next  為了下面如果next改變后不滿足，                 next._row--;//上                          
		if (CheckisAccess(a, n, next))
		{
			cur = next;
			paths.push(cur);
			continue;
		}
	
		next = cur;
		next._col++;//右
		if (CheckisAccess(a, n, next))
		{
			cur = next;
			paths.push(cur);
			continue;
		}
		next = cur;
		next._row++;//下
		if (CheckisAccess(a, n, next))
		{
			cur = next;
			paths.push(cur);
			continue;
		}
		next = cur;
		next._col--;// 左
		if (CheckisAccess(a, n, next))
		{
			cur = next;
			paths.push(cur);
			continue;
		}
		next = cur;
		paths.pop();     //如果遇到不通（在此即四個(gè)方向都不為0）然后，讓棧中保存
	}                              的坐標(biāo)pop（即往回倒）重復(fù)試探四個(gè)方向 直到找到另一
	
	return false;                   條可通路徑；
}
void display(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;
	}

}

 至此，一個(gè)簡(jiǎn)單的迷宮就完成了，以上左邊的圖就是開始的迷宮。右邊的圖是結(jié)果。最終，每次走過的地方都被標(biāo)志成2.

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

當(dāng)前標(biāo)題：實(shí)現(xiàn)簡(jiǎn)單的迷宮-創(chuàng)新互聯(lián)
本文來源：http://aaarwkj.com/article28/ppdcp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、ChatGPT、電子商務(wù)、品牌網(wǎng)站設(shè)計(jì)、做網(wǎng)站、微信小程序

廣告

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