首页 > 其他 > 详细

Maze迷宫问题

时间:2016-04-16 19:33:37      阅读:218      评论:0      收藏:0      [点我收藏+]

迷宫地形我们可以通过读文件的形式,通过已知入口逐个遍历坐标寻找通路。

文件如图:

技术分享

每个坐标的位置用Pos来记录:

struct Pos    //位置坐标
{
   int  _row;
   int _col;
};

定义行列范围

#define M 10   //行
#define N 10   //列

初始化迷宫数组
将通过读文件的方式获取的字符转成整型数据,保存在M行N列的数组中。

void InitMaze(int* maze)
{	
	struct WavHeadhWAV;
	FILE* fout = fopen("MazeMap.txt", "r");   // .txt文件要放在当前目录下
	if (fout == NULL)                       // 这里一定要检查读文件是否成功
	{
		cout << "can‘t find MazeMap.txt !" << endl<<endl;
		return;
	}
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N;)
		{
			char ch = fgetc(fout);
			if (ch==‘1‘||ch==‘0‘)
			{
				maze[i*N + j] = ch - ‘0‘;
				j++;
			}
		}
	}
	fclose(fout);
}

回溯查找通路

利用栈来存储通路,通过上下左右四个方向依次遍历,如果该位置满足条件,就将它入栈,并将该位置的数据置为2;如果四个方向都不满足条件就执行出栈操作,回溯查找满足条件的位置(这时候如果栈为空了,说明查找通路失败),继续循环遍历,直到找到出口为止。

这里建立一个最小栈,如果找到出路,就将该栈赋给最小栈,并将出口置为1,继续回溯查找通路,如果又一次找到通路,就将该栈的长度与最小栈进行比较,如果该栈长度比最小栈还要小,就将它再一次赋给最小栈(保证最小栈是最短的通路),继续回溯,直到整个栈为空,回到了入口,程序结束。

bool SearchMazePath(int *maze, Pos entry, stack<Pos>& paths)   // 利用栈回溯查找通路,并实现迷宫的最优解
{
	assert(maze);
	stack<Pos>min;
	paths.push(entry);
	while (!paths.empty())
	{
		Pos cur = paths.top();
		maze[cur._row*N+cur._col] = 2;
		if (cur._row==M-1)
		{
			if (paths.size()< min.size() || min.size() == 0)
			{
				min = paths;
			}
			paths.pop();
			maze[min.top()._row*N + min.top()._col] = 1;
		}	
		Pos next = cur;
		next._col--;  //左
		if (CheckIsAccess(maze, next))
		{
			paths.push(next);
			maze[next._row*N + next._col] = 2;
			continue;
		}
		next = cur;
		next._col++; //右
		if (CheckIsAccess(maze, next))
		{
			paths.push(next);
			maze[next._row*N + next._col] = 2;
			continue;
		}
		next = cur;
		next._row--; //上
		if (CheckIsAccess(maze, next))
		{
			paths.push(next);
			maze[next._row*N + next._col] = 2;
			continue;
		}
		next = cur;
		next._row++; //下
		if (CheckIsAccess(maze, next))
		{
			paths.push(next);
			maze[next._row*N + next._col] = 2;
			continue;
		}
		paths.pop();
	}
	if (paths.empty()&&!min.empty())
	{
			maze[min.top()._row*N + min.top()._col] = 2;
			return true;
	}
	return false;
}

检查该位置是否合法:(坐标在行列范围之内)

bool CheckIsAccess(int* maze, const Pos& next)    // 检查该位置是否合法
{
	assert(maze);
	if ((next._row >= 0 && next._row <= N) && (next._col >= 0 && next._col < M) && maze[next._row*N + next._col] == 0)
	{
		return true;
	}
	return false;
}

打印迷宫:

void PrintMaze(int *maze)   // 打印迷宫
{
	assert(maze);
	for (int i = 0; i < M; i++)
	{ 
		for (int j = 0; j < N; j++)
		{
			cout << maze[i*N + j] <<" " ;
		}
		cout << endl;
	}
	cout << endl;  
}

技术分享

本文出自 “言安阳” 博客,谢绝转载!

Maze迷宫问题

原文:http://iynu17.blog.51cto.com/10734157/1764550

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!