【转】算法基础(二):栈的应用 --- 迷宫解题

来源:https://software.intel.com/zh-cn/blogs/2014/03/03/?utm_campaign=CSDN&utm_source=intel.csdn.net&utm_medium=Link&utm_content=%20others-%20suanfa

注:为了不离开本节讨论的重点--栈,迷宫的自动生成以后重新写。这里用简单的二维数组代替,手动迷宫,呵呵!

MAP里面0代表墙(通不过),1代表空格(可通过)代码中每一步有详细注释。欢迎大家交流,嘻嘻。

【转】算法基础(二):栈的应用 --- 迷宫解题【转】算法基础(二):栈的应用 --- 迷宫解题
  1 // DataStructure_ZJC.cpp : 定义控制台应用程序的入口点。  
  2 /* 
  3 二. 栈的应用-迷宫解题 
  4 */  
  5 #include "stdafx.h"  
  6 #include<stdio.h>  
  7 #include<malloc.h>  
  8 #include<stdlib.h>  
  9   
 10 #define TRUE  1   
 11 #define FALSE 0  
 12 #define OK    1  
 13 #define ERROR 0  
 14 #define INFEASIBLE -1  
 15 #define OVERFLOW   -2  
 16   
 17 typedef struct  
 18 {  
 19     int x;          //x坐标  
 20     int y;          //y坐标  
 21 }Postype;           //坐标类型  
 22 typedef struct  
 23 {  
 24     //int ord;      //通道块在路径上的序号  
 25     //Postype seat; //通道块在迷宫中的坐标  
 26     //int di;       //从此通道块走向下一通道块的“方向”  
 27     int x;  
 28     int y;          //元素坐标  
 29   
 30 //  bool track;     //是否已经走过  
 31 }ElemType;          //栈的元素类型  
 32   
 33 int MAP[9][9] =     /*二维数组就够用了,先从简单的地图开始*/  
 34 {    
 35    //0 1 2 3 4 5 6 7 8  
 36        
 37      0,0,0,0,0,0,0,0,0,  
 38      0,1,0,0,1,1,1,1,0,  
 39      0,1,0,0,1,1,1,1,0,  
 40      0,1,1,1,1,0,1,1,0,  
 41      0,1,0,1,0,1,1,1,0,  
 42      0,1,0,1,0,1,1,1,0,  
 43      0,1,0,1,0,1,1,1,0,  
 44      0,0,0,1,1,1,1,1,0,  
 45      0,0,0,0,0,0,0,0,0,  
 46   
 47   
 48 };  
 49 /*-------------------------------------栈的元素类型定义完毕-------------------------*/  
 50 typedef int Status;     //函数返回值  
 51   
 52 #define STACK_INIT_SIZE 100     // 栈的初始大小  
 53 #define STACK_INCREMENT 10      // 每次增加的空间大小  
 54   
 55   
 56 //下面给出栈的相关定义  
 57 typedef struct  
 58 {  
 59     ElemType *base;     //在构造栈之前和销毁之后,base的值为NULL  
 60     ElemType *top;      //栈顶指针  
 61     int stacksize;      //当前已分配的存储空间,以元素为单位  
 62 }ZJC_Stack;  
 63   
 64 //--------------------------------------栈基本操作的算法部分--------------------------   
 65 //栈的初始化  
 66 Status InitStack(ZJC_Stack &S)    
 67 {  
 68        
 69     S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));    //分配内存空间  
 70     if(!S.base)            
 71         exit(OVERFLOW);  
 72       
 73     else                //否则分配成功  
 74     {  
 75         S.top = S.base;    
 76         S.stacksize  = STACK_INIT_SIZE;    
 77         return  OK;  
 78     }  
 79   
 80 }  
 81                         //获得栈顶元素  
 82 ElemType GetTop(ZJC_Stack S)  
 83 {      
 84     if(S.top == S.base )  
 85         exit(ERROR);       
 86     return *(S.top - 1);       
 87 }  
 88 //压栈  
 89 Status Push(ZJC_Stack &S,ElemType e)  
 90 {                      
 91     if(S.top - S.base >= S.stacksize)       
 92     {  
 93         S.base = (ElemType*)realloc(S.base,(S.stacksize + STACK_INCREMENT) * sizeof(ElemType));  
 94         if(!S.base)  
 95             exit(OVERFLOW);  
 96         S.stacksize += STACK_INCREMENT;        
 97         S.top = S.base + S.stacksize;         
 98     }  
 99     *S.top++ = e;  
100     return OK;  
101 }  
102 void Print_Path(ZJC_Stack S)    //打印出栈中的元素  
103 {  
104     printf("\n寻路完成..路径坐标值如下:......\n");  
105     ElemType *p = S.base;       //首先p指向栈底指针  
106     ElemType temp;     
107     while( p != S.top)          //只要没有到顶端,指针就移动,然后输出元素值  
108     {  
109         temp = *p;  
110         printf("\n路径 x = %d , y = %d",temp.x,temp.y);  
111         p++;          
112     }  
113 }  
114   
115 //出栈函数  
116 Status Pop(ZJC_Stack &S,ElemType &e)  
117 {  
118     if(S.top == S.base      )   //空栈,返回错误  
119     return ERROR;  
120     else                        //不是空栈  
121     {         
122         e = * --S.top;  
123         return OK;  
124     }  
125 }  
126 void PathAddToStack(int i,int j,ElemType temp,ZJC_Stack &robot)     //因为要修改值,所以取地址,开始没加取地址符号,栈顶元素一直是(1,1)  
127 {  
128     temp.x = i,temp.y = j;  
129     Push(robot,temp);  
130     MAP[i][j] = 2;                      //标记已经走过该格子了,当初想是否需要用其他标记,实际上不需要的,既然标记2,那么证明当然可以走过(不是墙)!  
131 }  
132 void MAZH_SOLVE(int endx,int endy)      //解决迷宫问题函数,参数为终点的坐标  
133 {                             
134     int i = 1,j = 1;                    //起点坐标    
135     ZJC_Stack robot;                    //定义栈;  
136     if(InitStack( robot ) )             //初始化栈  
137         printf("\n栈的初始化完成....\n");                                        
138     ElemType CurrentPos ;               //当前位置         
139     ElemType start;                     //初始位置的相关信息  
140     ElemType temp;                      //暂时用的  
141     start.x = i;  
142     start.y = j;  
143     temp = start;  
144     //start.track = true;               //Robot站在初始位置,初始位置已经走过  
145     MAP[i][j] = 2;                      //走过的标记为2             
146     Push(robot,start);                  //初始位置入栈  
147     printf("\n开始寻路....\n");   
148     do                                  //主要寻路算法:  
149     {  
150           
151           CurrentPos = GetTop(robot);  
152           i = CurrentPos.x;  
153           j = CurrentPos.y;  
154           printf(" \n寻路过程如下栈顶元素的 x = %d ,y = %d....\n",i,j);  
155           if(MAP[i][j+1] == 1)          //表明向下一格走得通  
156           {                                       
157               printf("\n向下能走动");    //向下前进一步,压栈,标记  
158               j++;  
159               PathAddToStack(i,j,temp,robot);                             
160           }  
161           else if( MAP[i + 1][j] == 1)         
162           {  
163                printf("\n向右能走动");  
164                 i++;                           
165                 PathAddToStack(i,j,temp,robot);  
166           }  
167           else  if(MAP[i - 1][j] == 1)          
168           {  
169                printf("\n向左能走动");  
170                 i--;                           
171                 PathAddToStack(i,j,temp,robot);  
172           }  
173           else if(MAP[i][j - 1] == 1)          
174           {  
175                printf("\n向上能走动");  
176                 j--;                           
177                 PathAddToStack(i,j,temp,robot);  
178           }  
179           else  //都走不动  
180           {  
181                printf("\n都走不动,退栈");                           
182                Pop(robot,temp);  
183           }  
184       
185     }while( GetTop(robot).x != endx || GetTop(robot).y != endy);        //只要栈顶元素的x,y不等于终点坐标的x,y,则一直循环找路径  
186     printf("\n完成!\n");  
187     Print_Path(robot);                  //打印出坐标值                               
188 }  
189 int _tmain(int argc, _TCHAR* argv[])    //入口函数  
190 {      
191     MAZH_SOLVE(7,7);       
192     return 0;  
193 }
View Code

其实在开始判断一下起点与终点的相对位置,选择不同的方案,这样可以减少后面的某些判断次数,提高效率。

比如我的这张地图中,就应该优先判断右下,因为终点在右下角。开始判断一下相对位置,后面修改下if条件句的顺序,就能提高效率了。

运行结果:

【转】算法基础(二):栈的应用 --- 迷宫解题

【转】算法基础(二):栈的应用 --- 迷宫解题

【转】算法基础(二):栈的应用 --- 迷宫解题

 

上一篇:创建企业级品质数据湖 Spark没那么简单


下一篇:Fdog系列(一):思来想去,不如写一个聊天软件,那就从仿QQ注册页面开始吧。