实现简单的迷宫-创新互联

我们知道栈的特点是：后进先出（First In Last Out）;也就是说只能在栈的尾部进

为阿克苏等地区用户提供了全套网页设计制作服务，及阿克苏网站建设行业解决方案。主营业务为网站制作、成都网站设计、阿克苏网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

行压栈和出栈，而且出栈的时候只能从最后一个数据开始。

  所以我们利用栈这个特点，来实现这个迷宫。在这之中我们要采用“回溯”的方法去处理当遇到路径不通的情况。

  原理：每找到一个通路，就将这个数据压栈，这样当前位置的上一个位置就位于栈的顶部，假如当前位置的上下左右都找不到通路的时候，就开始回溯，也就是开始从来的路往回走，而之前走过的路都存在栈里面，所以只需要一个一个的Pop就能依次往回退，每退一次，就寻找上下左右有没有通路，如果找到通路就继续往下走，并压栈，直到走出整个迷宫。

#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') //只读有效的字符，遇空格不转换
			{
				a[i * n + j] = ch - '0';
				j++;
			}
			else
			{
				continue;
			}
		}
	}
	fclose(fout);
}
bool CheckisAccess(int *a, int n, const pos& next)//检查当前的路径是否通行
{
	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);     //将入口地址（坐标）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();     //如果遇到不通（在此即四个方向都不为0）然后，让栈中保存
	}                              的坐标pop（即往回倒）重复试探四个方向 直到找到另一
	
	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;
	}

}

 至此，一个简单的迷宫就完成了，以上左边的图就是开始的迷宫。右边的图是结果。最终，每次走过的地方都被标志成2.

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

当前标题：实现简单的迷宫-创新互联
本文来源：https://www.cdcxhl.com/article28/ppdcp.html

成都网站建设公司_创新互联，为您提供商城网站、ChatGPT、电子商务、品牌网站设计、做网站、微信小程序

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联