回溯思想解决迷宫问题

发表于： 2018-04-25 分类于：数据结构与算法

字数： 1408 阅读：≈ 3分钟浏览：评论：

这是几个由二维数组构成的迷宫，简单的迷宫，多通路不带环的迷宫，多通路带环的迷宫！对于简单迷宫我们需要判断是否有出口！对于多通路不带环的迷宫我们需要确定出口并且判断最短路径，对于通路间带环的迷宫我们需要找出最短路径！

算法思想：回溯

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。在本题中也用到的就是回溯，就是把走过的点坐标压栈，遇到无路可走的情况就开始回溯，也就是出栈！总体思路就是：

现将入口点压栈，走过的地方标记为2
每走一步就将坐标压栈，判断下一步可以走的地方，如果能走就压栈
当上下左右四个方向都不能走的时候就回溯
直到回溯到入口点还是没有其他方向可以走，那么循环结束，也就意味着没有出口！
使用一个方法判断坐标点是否合法的，注意数组越界的情况，首先不越界，其次坐标点值为1的时候才是合法的
对于多通路迷宫首先需要明白当右边出现两个入口点的时候只需要判断列 == N即可认为是找到了出口
首先下一个点可以走的条件是：该点值为1或者该点值比上一个+1还大
每走一步值就+1，入口点值设置为2

代码实现

所有代码位于GitHub：https://github.com/zouchanglin/VSworkspace/tree/master/67_Maze，对于简单迷宫的核心代码：

int CheckAccess(Pos next)
{
	//判断越界的情况
	if(next._col >= 0 &&next._row>=0
		&& next._col<N && next._row<N)
	{ 
		//1才是表示通路
		if (maze[next._row][next._col] == 1) 
		{
			return 1;
		}
	}
	//return 0表示不可以通过
	return 0;
}
int MazeGetPath(Pos entry,Pos exit)
{
	Pos cur = entry;//cur记录起始位置
	
	Stack path;
	StackInit(&path);
	StackPush(&path, entry);//将起始坐标压栈
	while (StackEmpty(&path))
	{
		cur = StackTop(&path);
		if ((cur._row == exit._row) && (cur._col == exit._col))
			return 1;
		//探测下一次可以去的地方
		maze[cur._row][cur._col] = 2;//标记上一次走过的位置
		//上
		Pos next = cur;
		next._row -= 1;
		if (CheckAccess(next)) 
		{
			StackPush(&path, next);
			continue;
		}
		//下
		next = cur;
		next._row += 1;
		if (CheckAccess(next))
		{
			StackPush(&path, next);
			continue;
		}
		//左
		next = cur;
		next._col -= 1;
		if (CheckAccess(next))
		{
			StackPush(&path, next);
			continue;
		}
		//右
		next = cur;
		next._col += 1;
		if (CheckAccess(next))
		{
			StackPush(&path, next);
			continue;
		}

		//回溯
		StackPop(&path);
	}
	return 0;
}

对于稍复杂的迷宫的核心代码

int CheckAccess(Pos next)
{
	//判断越界的情况
	if(next._col >= 0 &&next._row>=0
		&& next._col<N && next._row<N)
	{ 
		//1才是表示通路
		if (maze[next._row][next._col] == 1) 
		{
			return 1;
		}
	}
	//return 0表示不可以通过
	return 0;
}

int MazeCheckIsAccess(Pos cur, Pos next)
{
	//判断越界的情况
	if ((next._col >= 0 && next._row >= 0 && next._col<N && next._row<N)
		&&(maze[next._row][next._col] == 1 || maze[next._row][next._col]>maze[cur._row][cur._col]+1))
	{
			return 1;
	}
	//return 0表示不可以通过
	return 0;
}

int pathsize = 0;

int MazeGetPath(Pos entry,Pos exit)
{
	Pos cur = entry;//cur记录起始位置
	
	Stack path;
	StackInit(&path);
	StackPush(&path, entry);//将起始坐标压栈

	maze[entry._row][entry._col] = 2;
	while (StackEmpty(&path))
	{
		cur = StackTop(&path);
		maze[cur._row][cur._col] = 2;//标记上一次走过的位置
		//if ((cur._row == exit._row) && (cur._col == exit._col))
		if (cur._col == 5) 
		{
			//如果只找一条通路则返回
			//return 1;
			//StackDestory(&path);
			if (pathsize == 0||
				StackSize(&path) < pathsize)
			{
				pathsize = StackSize(&path);
			}
		}
		//探测下一次可以去的地方
		//上
		Pos next = cur;
		next._row -= 1;
		if (CheckAccess(next)) 
		{
			StackPush(&path, next);
			continue;
		}
		//下
		next = cur;
		next._row += 1;
		if (CheckAccess(next))
		{
			StackPush(&path, next);
			continue;
		}
		//左
		next = cur;
		next._col -= 1;
		if (CheckAccess(next))
		{
			StackPush(&path, next);
			continue;
		}
		//右
		next = cur;
		next._col += 1;
		if (CheckAccess(next))
		{
			StackPush(&path, next);
			continue;
		}

		//回溯
		StackPop(&path);
	}
	return 0;
}


int MazeGetShortPath(Pos entry, Pos exit)
{
	Pos cur = entry;//cur记录起始位置

	Stack path;
	StackInit(&path);
	StackPush(&path, entry);//将起始坐标压栈


	maze[entry._row][entry._col] = 2;
	while (StackEmpty(&path))
	{
		cur = StackTop(&path);
		if (cur._col == 5)
		{
			//如果只找一条通路则返回
			//return 1;
			//StackDestory(&path);
			if (pathsize == 0 ||
				StackSize(&path) < pathsize)
			{
				pathsize = StackSize(&path);
			}
		}
		//探测下一次可以去的地方
		//上
		Pos next = cur;
		next._row -= 1;
		if (MazeCheckIsAccess(cur, next))
		{
			maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
			StackPush(&path, next);
			continue;
		}
		//下
		next = cur;
		next._row += 1;
		if (MazeCheckIsAccess(cur, next))
		{
			maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
			StackPush(&path, next);
			continue;
		}
		//左
		next = cur;
		next._col -= 1;
		if (MazeCheckIsAccess(cur, next))
		{
			maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
			StackPush(&path, next);
			continue;
		}
		//右
		next = cur;
		next._col += 1;
		if (MazeCheckIsAccess(cur, next))
		{
			maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
			StackPush(&path, next);
			continue;
		}

		//回溯
		StackPop(&path);
	}
	return 0;
}