回溯思想解决迷宫问题

数据结构与算法

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

算法思想：回溯

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

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

    代码实现

    所有代码位于 GitHub：https://github.com/zouchanglin/VSworkspace/tree/master/67_Maze，对于简单迷宫的核心代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    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;
    }
    对于稍复杂的迷宫的核心代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    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;
    }
    mark
    mark
数据结构与算法