数据结构之栈的应用----迷宫求解


/***********程序设计思想*************/
（1）迷宫地图相关：
利用动态二维数组来初步勾勒出迷宫：
建议先用malloc申请一维数组，再用calloc申请每个元素中的一维数组，因为我用的是1来表示迷宫的通路，0表示死路，calloc申请完后就会自动初始化为0
迷宫交岔路结点：
我们要有一个扫描通路的函数，对一个坐标进行东南西北的扫描，当遇到交岔路的坐标时，需要将所有的通路存入一个数组，扫描从东开始，至北结束，逆时针方向
这里设计的是单通道迷宫，也就是说不会有并行的通路，扫描出来的通路是不会超过两个的（肯定是不允许把结点来的那个原始方向认为是通路的）
当我们按着第一个方向走到死路时，我们需要返回到最近的一个交岔路结点，这之后第一个最重要的操作便是：将已确定的死路给封死，即把那个坐标的值从1改为0。
（2）栈相关：
栈在这里需要两个，一个存放走过的路径，也就是移动到一个坐标，就把这个坐标入栈，另一个是存放交岔路结点的，当我们遇到死路之后，就需要从交岔路结点栈中
弹出一个元素A，然后从所有路径的栈中一直弹出元素（就是原路返回），直到栈顶元素B与A相等，就表明已经退回到了最近的一个交岔路口
下一步便是走向另一个通路，直到遇到死路或终点
（3）设计根本：
整个程序是建立在递归应用中的，抽象出来就是：当我们规定一个优先方向（默认为东方向吧）、再规定一个固定的旋转方向（默认为逆时针）之后，我们会有一个从东方、
沿逆时针、到北方的总体走向，遇到一个死胡同，我们就要沿着路径原路返回，直到遇到一个十字路口，再走向另一个可通的方向，要是还是死胡同，就返回到再前一个十字
路口，进入另一个可通的方向，如此反复的探索，知道走到终点。
/***********程序设计细节*************/
（1）扫描通道函数----int Scan_Direction(data_type elem,int *all_direction,int **labyrinth);
返回值：返回所有可通方向的数量，可能值为0，1，2
重要参数：all_direction：记录所有可通的方向
关键实现：
  1. if(labyrinth[elem.x][elem.y+1] == YES && elem.direction != EAST)  
  2. {  
  3.     direction = EAST;  
  4.     all_direction[i++] = EAST;  
  5. }  
坐标是按照二维数组的行列来规定的，这里给出的是判断当前坐标的东向是可通，YES表明可通，当坐标的东邻坐标（[elem.x][elem.y+1]）值为YES的时候，我们并不能
确定它的东方向就是可通的，因为有一种例外：当这个坐标就是从它的东邻坐标移过来的时候，这个坐标当然是可通的，所以在if的判断语句中还应加上一个判断语句：
elem.direction != EAST，只有当这两个条件同时满足的时候才表明东邻为通，其余三个方向的判断与之类似

（2）根据方向的数目来走迷宫

case 1：先看只有一个方向可走到时候

这种情况很好解决，按着扫描的方向走一步就OK，让移动后的坐标入栈即可，这里我遇到了一个小问题，就是由于很多次的往回走，每一次都要入栈或出栈，貌似这样可能

造成路径栈中存在几个相同的坐标，并且这些坐标在栈中都是相邻的，所以我在每次入栈的时候都判断了一下，如果和栈顶元素相同，就不入栈了，以免最后弹出正确路径的

时候出现多个重复的坐标

case 2：这个条件是程序的关键部分，总的来说就是先走一个方向，若未遇到终点，就返回到交岔路结点，再走向另一条路，反复直到走到终点

  1. case 2:  
  2. {  
  3.     Push_Stack(&cross_point,position);  
  4.     GetElem_Stack(&path,&top_path);  
  5.     if(top_path.x != position.x || top_path.y != position.y)  
  6.         Push_Stack(&path,position);  
  7.     Print_Position(position);  
  8.     Move_Path(&position,all_direction[0],&path,&cross_point,labyrinth);  
  9.     if(position.x == (LINE-2) && position.y == (ROW-2))  
  10.         break;  
  11.     Move_Path(&position,all_direction[1],&path,&cross_point,labyrinth);  
  12. }  
  13. break;  
首先让交岔路结点入栈（交叉点栈），让这个点入路径栈

接下来就是走向第一个方向，进入这个方向后，position将先通过all_direction[0]方向移动一格，然后利用递归，对新坐标进行扫描，判断出可通方向个数（0，1，2三种），

接着就开始重复昨天的故事，也就是递归了，当这一个方向走完后，这个Move_Path就结束了，然后判断是否到了终点，如果不是终点就进入第二个Move_Path，继续递归，

  • 1
  • 2
  • 下一页

相关内容