/***********程序设计思想*************/
(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:记录所有可通的方向
关键实现:
if(labyrinth[elem.x][elem.y+1] == YES && elem.direction != EAST) { direction = EAST; all_direction[i++] = EAST; }
坐标是按照二维数组的行列来规定的,这里给出的是判断当前坐标的东向是可通,YES表明可通,当坐标的东邻坐标([elem.x][elem.y+1])值为YES的时候,我们并不能确定它的东方向就是可通的,因为有一种例外:当这个坐标就是从它的东邻坐标移过来的时候,这个坐标当然是可通的,所以在if的判断语句中还应加上一个判断语句:
elem.direction != EAST,只有当这两个条件同时满足的时候才表明东邻为通,其余三个方向的判断与之类似
(2)根据方向的数目来走迷宫
case 1:先看只有一个方向可走到时候
这种情况很好解决,按着扫描的方向走一步就OK,让移动后的坐标入栈即可,这里我遇到了一个小问题,就是由于很多次的往回走,每一次都要入栈或出栈,貌似这样可能
造成路径栈中存在几个相同的坐标,并且这些坐标在栈中都是相邻的,所以我在每次入栈的时候都判断了一下,如果和栈顶元素相同,就不入栈了,以免最后弹出正确路径的
时候出现多个重复的坐标
case 2:这个条件是程序的关键部分,总的来说就是先走一个方向,若未遇到终点,就返回到交岔路结点,再走向另一条路,反复直到走到终点
case 2: { Push_Stack(&cross_point,position); GetElem_Stack(&path,&top_path); if(top_path.x != position.x || top_path.y != position.y) Push_Stack(&path,position); Print_Position(position); Move_Path(&position,all_direction[0],&path,&cross_point,labyrinth); if(position.x == (LINE-2) && position.y == (ROW-2)) break; Move_Path(&position,all_direction[1],&path,&cross_point,labyrinth); } break;
首先让交岔路结点入栈(交叉点栈),让这个点入路径栈