数据结构

数据结构之迷宫求解

为了找工作,最近看了一段时间的数据结构,看得头昏脑涨,二叉树的递归遍历与查找,递归来递归去都给递归晕了,函数指针,指向指针的指针,指来指去,已经指向云彩里了。往往一个小问题都需要纠结好久,花费几十分钟乃至几个小时的时间,真有点感觉自己不适合搞程序设计,心中万分失落。哎,想要混一口饭吃真不容易,但是除了这些真不知道还能干些什么。

在学习数据结构的过程中发现在面对一个问题,自己的思路不清,缺少归纳,往往想出一个大致方法,就急于去用程序求解,具体实现的时候上发现犯了很多错误乃至于进入死胡同。没办法学习总归还是要去学习,习惯也要慢慢去培养。虽然学习的过程中有纠结,有痛苦,但是也会有一些有趣的东西,或者解决出某一个问题的成就感(虽然不值得一提)。不管怎样,只要每天都在进步,这样也就够了。

在学习数据结构时,遇到一个迷宫求解的例题,感觉比较有趣,写出记录一些,就当作是对痛苦的学习过程的一种纪念吧。

迷宫求解

迷宫求解

求解方法:

  1. 判断当前位置是否可通,即该位置不为墙,也不是已走过的方块
  2. 若当前位置可通,位置加入路径堆栈,留下脚印,寻找下一个相邻的方块
  3. 寻找下一个相邻方块的方法:先向东寻找,若东边相邻方块不可通,顺时针方向继续寻找,寻找到相邻可通方块后,此相邻方块设为当前位置。若东西南北方相邻方块均不可通,则设置当前位置为不可通,并从路径堆栈中删除该方块,然后获取路径中最后一个方块为当前位置(即后退一步)。
  4. 若当前位置不可通,则寻找相邻为位置是否可通(寻找方法同3)。相邻位置可通,则该相邻位置设为当前位置;相邻位置均不可通,则该位置从路径堆栈中删除,获取路径中最后一个方块为当前位置(即后退一步)。
  5. 重复以上步骤,直至找到出口或者路径堆栈为空,且起始点不可通(未找到出口)。

迷宫求解代码: