回溯思想解决迷宫问题

发表于： 分类于：
字数： 1619 阅读：≈ 4分钟 浏览： 评论：

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

算法思想：回溯

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

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

代码实现

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

 1int CheckAccess(Pos next)
 2{
 3	//判断越界的情况
 4	if(next._col >= 0 &&next._row>=0
 5		&& next._col<N && next._row<N)
 6	{ 
 7		//1才是表示通路
 8		if (maze[next._row][next._col] == 1) 
 9		{
10			return 1;
11		}
12	}
13	//return 0表示不可以通过
14	return 0;
15}
16int MazeGetPath(Pos entry,Pos exit)
17{
18	Pos cur = entry;//cur记录起始位置
19	
20	Stack path;
21	StackInit(&path);
22	StackPush(&path, entry);//将起始坐标压栈
23	while (StackEmpty(&path))
24	{
25		cur = StackTop(&path);
26		if ((cur._row == exit._row) && (cur._col == exit._col))
27			return 1;
28		//探测下一次可以去的地方
29		maze[cur._row][cur._col] = 2;//标记上一次走过的位置
30		//上
31		Pos next = cur;
32		next._row -= 1;
33		if (CheckAccess(next)) 
34		{
35			StackPush(&path, next);
36			continue;
37		}
38		//下
39		next = cur;
40		next._row += 1;
41		if (CheckAccess(next))
42		{
43			StackPush(&path, next);
44			continue;
45		}
46		//左
47		next = cur;
48		next._col -= 1;
49		if (CheckAccess(next))
50		{
51			StackPush(&path, next);
52			continue;
53		}
54		//右
55		next = cur;
56		next._col += 1;
57		if (CheckAccess(next))
58		{
59			StackPush(&path, next);
60			continue;
61		}
62
63		//回溯
64		StackPop(&path);
65	}
66	return 0;
67}

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

  1int CheckAccess(Pos next)
  2{
  3	//判断越界的情况
  4	if(next._col >= 0 &&next._row>=0
  5		&& next._col<N && next._row<N)
  6	{ 
  7		//1才是表示通路
  8		if (maze[next._row][next._col] == 1) 
  9		{
 10			return 1;
 11		}
 12	}
 13	//return 0表示不可以通过
 14	return 0;
 15}
 16
 17int MazeCheckIsAccess(Pos cur, Pos next)
 18{
 19	//判断越界的情况
 20	if ((next._col >= 0 && next._row >= 0 && next._col<N && next._row<N)
 21		&&(maze[next._row][next._col] == 1 || maze[next._row][next._col]>maze[cur._row][cur._col]+1))
 22	{
 23			return 1;
 24	}
 25	//return 0表示不可以通过
 26	return 0;
 27}
 28
 29int pathsize = 0;
 30
 31int MazeGetPath(Pos entry,Pos exit)
 32{
 33	Pos cur = entry;//cur记录起始位置
 34	
 35	Stack path;
 36	StackInit(&path);
 37	StackPush(&path, entry);//将起始坐标压栈
 38
 39	maze[entry._row][entry._col] = 2;
 40	while (StackEmpty(&path))
 41	{
 42		cur = StackTop(&path);
 43		maze[cur._row][cur._col] = 2;//标记上一次走过的位置
 44		//if ((cur._row == exit._row) && (cur._col == exit._col))
 45		if (cur._col == 5) 
 46		{
 47			//如果只找一条通路则返回
 48			//return 1;
 49			//StackDestory(&path);
 50			if (pathsize == 0||
 51				StackSize(&path) < pathsize)
 52			{
 53				pathsize = StackSize(&path);
 54			}
 55		}
 56		//探测下一次可以去的地方
 57		//上
 58		Pos next = cur;
 59		next._row -= 1;
 60		if (CheckAccess(next)) 
 61		{
 62			StackPush(&path, next);
 63			continue;
 64		}
 65		//下
 66		next = cur;
 67		next._row += 1;
 68		if (CheckAccess(next))
 69		{
 70			StackPush(&path, next);
 71			continue;
 72		}
 73		//左
 74		next = cur;
 75		next._col -= 1;
 76		if (CheckAccess(next))
 77		{
 78			StackPush(&path, next);
 79			continue;
 80		}
 81		//右
 82		next = cur;
 83		next._col += 1;
 84		if (CheckAccess(next))
 85		{
 86			StackPush(&path, next);
 87			continue;
 88		}
 89
 90		//回溯
 91		StackPop(&path);
 92	}
 93	return 0;
 94}
 95
 96
 97int MazeGetShortPath(Pos entry, Pos exit)
 98{
 99	Pos cur = entry;//cur记录起始位置
100
101	Stack path;
102	StackInit(&path);
103	StackPush(&path, entry);//将起始坐标压栈
104
105
106	maze[entry._row][entry._col] = 2;
107	while (StackEmpty(&path))
108	{
109		cur = StackTop(&path);
110		if (cur._col == 5)
111		{
112			//如果只找一条通路则返回
113			//return 1;
114			//StackDestory(&path);
115			if (pathsize == 0 ||
116				StackSize(&path) < pathsize)
117			{
118				pathsize = StackSize(&path);
119			}
120		}
121		//探测下一次可以去的地方
122		//上
123		Pos next = cur;
124		next._row -= 1;
125		if (MazeCheckIsAccess(cur, next))
126		{
127			maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
128			StackPush(&path, next);
129			continue;
130		}
131		//下
132		next = cur;
133		next._row += 1;
134		if (MazeCheckIsAccess(cur, next))
135		{
136			maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
137			StackPush(&path, next);
138			continue;
139		}
140		//左
141		next = cur;
142		next._col -= 1;
143		if (MazeCheckIsAccess(cur, next))
144		{
145			maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
146			StackPush(&path, next);
147			continue;
148		}
149		//右
150		next = cur;
151		next._col += 1;
152		if (MazeCheckIsAccess(cur, next))
153		{
154			maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
155			StackPush(&path, next);
156			continue;
157		}
158
159		//回溯
160		StackPop(&path);
161	}
162	return 0;
163}

mark mark