前面多篇推文已经介绍了整个课设的绝大部分内容，本文是迷宫求解系列的最后一篇推文。
本文将介绍最后一种寻找迷宫出路的方法，复杂度较高，文末也将对此次课设进行总结。
01新的思路此次介绍的求解迷宫的方法，说起来很简单，这一方法在实现之前经过了反复思考与确认，最终也实际验证过，简单来说是一种预处理的方法。
遍历迷宫矩阵，将所有的死胡同堵上。
总结起来只有上面这一句话，但是如何实现就是一个难题了，首先是如何定义这个死胡同。四周都是墙壁那肯定是死胡同，问题是生成的迷宫里面不会有那种四周都是墙壁的，所有应当是三面是墙壁，只有一面是道路，这才是死胡同，把这个位置标记为死胡同。
但是只标记这个位置就行了吗？它只有一面是道路，可是和它相邻的这个道路也有可能是属于死胡同的一部分，只是把死胡同的尽头那个位置标记上显然是不够的，所以我们还需要在标记一个位置之后，对它的唯一邻居也进行判断，接下来是邻居的邻居,.........。直到某一个位置不止一个邻居，那么它显然就不属于死胡同，或者说当前不能确定它是死胡同的一部分，这时候才结束判断。
有了上述关于一个位置是否为死胡同的判断标准之后，就可以开始接下来的内容了。
02思路实现先思考下我们需要什么？
判断一个位置是否只有唯一邻居，即该位置是否为死胡同。
如果一个位置只有唯一邻居，找到它唯一邻居的位置，重复上一步的判断。
其实说了很多，有一个很重要的地方还没有说明。我们对一个为死胡同的位置该如何标记的问题，由于此前的几个算法使用-1标记试探过的点，而这里死胡同并不属于试探过程，而是一个预处理过程，而且也为了表示上的统一，此处不使用-1标记死胡同，使用数字4标记。
实际上如果使用一个负数进行标记也会给判断死胡同带来麻烦。
标记过程可以看成是，将死胡同的尽头新砌一堵墙，死胡同的邻居就有可能成为砌墙之后的新死胡同的尽头了。
既然看成是新砌一堵墙，那么标记为什么不直接使用1呢，1不就代表墙壁吗，而且判断还更加方便。关于这个问题，这是因为我在课设中设置了重新初始化迷宫这一步，它的作用就是当按钮选择一个新算法，而没有改变迷宫等级的时候，直接沿用上一次的迷宫，将上一次迷宫的一些标记(如-1等)清除掉，这样也能够方便观察在同一个迷宫中不同算法的运行情况，而清除标记时无法对1进行清除。
基本的说明都在上面了，那么接下来就考虑那些是死胡同的情况。
情况一如上图所示，黑色代表墙壁，白色代表地面，红色代表已经标记的死胡同，我们需要做的就是判断出蓝色是死胡同就行。先说下红色这个是怎么判断的，三面都是墙壁，很容易判断。那么蓝色呢，也差不多的方法，直接使用四个if语句判断上下左右，之后的所有情况也都可以使用这种方法，这里不介绍这种方法。蓝色这一块，我是这么判断的，我们可以观察墙壁是1，红色方块是4，那么蓝色部分的四个邻居是1+1+4+0=6，暂时看不出什么，等后面几种情况分析完就能看出来了。
情况二如上图所示，显然蓝色方块应当被标记，这里仍然观察下四个邻居1+4+4+0=9.
情况三如上图所示，蓝色部分四个邻居应当是4+4+4+0=12.
至此应该能看出点什么了，尽头的红色是1+1+1+0=3。3、6、9、12都有了，我们能够利用它们判断这个点是否为死胡同或死胡同的一部分了，可能有读者会反应过来，四个邻居的数值之和对三取余数，取余数结果为0，即整除，说明应该将当前位置也标记为4。这样思考的方向是对的，但小的细节需要修改，如果一个结点的四周都是地面呢？0%3==0结果为true，这显然不行，另外我们还可以补充一个情况四，如果一个结点四面都是标记位4，即邻居之和为16，显然这个结点也应当被标记(实际上这种情况是否标记都不会影响寻找出路，为了统一，此处进行标记)。
所以最终判断是否一个位置只有唯一邻居(即该位置是死胡同或死胡同一部分)的代码如下所示。(如果不理解，可以直接使用四个if语句分别判断上下左右四个方向即可)
//判断是否只有唯一一个邻居privatestaticbooleanhasOnlyNeighbor(int[][]maze,inti,intj){intres=maze[i-1][j]+maze[i+1][j]+maze[j-1]+maze[j+1];//上+下+左+右return(res%3==0res!=0)
res==16;}
另外，在已知当前位置只有一个邻居之后，我们还需要移动到这个唯一邻居那里。找到唯一邻居的代码如下。
staticintmovearr[][]={{-1,0},{1,0},{0,-1},{0,1}};//上、下、左、右//在只有唯一邻居的前提下，找到这个唯一邻居publicstaticint[]findOnlyNeighbor(int[][]maze,inti,intj){intindex=0;if(maze[i-1][j]==0)index=0;elseif(maze[i+1][j]==0)index=1;elseif(maze[j-1]==0)index=2;elseif(maze[j+1]==0)index=3;returnmovearr[index];}
处理死胡同的代码如下：
//处理一个结点周围的同为死胡同一部分的邻居privatestaticvoiddealNeighbor(intmaze[][],intx,inty){intarr[];while(hasOnlyNeighbor(maze,x,y)!(x==mystart_xy==mystart_y)!(x==myend_xy==myend_y)){//当前位置为死胡同DrawMaze.drawMaze.drawRect(x,y,mylevel,1);sleep(L-mylevel*10L);maze[x][y]=4;//找出这个唯一邻居，它也可能是死胡同的一部分arr=findOnlyNeighbor(maze,x,y);x=x+arr[0];//移动到这个邻居处y=y+arr[1];}}
需要说明的是，这里mystart_x，mystart_y，myend_x，myend_y，mylevel被声明为了静态变量，也可以不声明为静态变量，使用传参的方式，但是参数列表为会比较长。
另外，判断一个位置是否为死胡同，要避开起始点和终点，这两个点容易误判。
主体部分的代码就是遍历矩阵，比较简单。
staticintmystart_x,mystart_y,myend_x,myend_y,mylevel;//预处理publicstaticvoidmyidea(intmaze[][],intstart_x,intstart_y,intend_x,intend_y,intlevel){mystart_x=start_x;mystart_y=start_y;myend_x=end_x;myend_y=end_y;mylevel=level;for(inti=start_x;i=end_x;i++){for(intj=start_y;j=end_y;j++){//预处理if(maze[j]==0!(i==start_xj==start_y)!(i==end_xj==end_y)){//非起点非终点的地面if(hasOnlyNeighbor(maze,i,j)){//只有一条路必然为死胡同maze[j]=4;//标记为死胡同，此处也可以不用标记，下方函数调用会标记dealNeighbor(maze,i,j);//死胡同周围很可能也是死胡同的一部分，继续处理周围的结点}}}}}
运行结果如下图所示。
处理完成之后只剩下一条主路，由于题目要求还要输出三元组，可以和之前一样，设置一个解析路径的函数，将路径解析出来，实际上，都已经处理到这一步了，直接调用之前写过的任何一个算法都可以直接找到出路了，例如直接预处理之后调用深搜即可。
03一点总结本次课设耗时一周(推文是课设验收后写的，拖的时间比较长)，从结果来看做的还可以，推文中介绍的只是主体部分内容，而最后提交的课设对许多细节做了优化与改进。例如增加不同等级的迷宫，多次点击等级，可以刷新迷宫，点击不同算法按钮，不会切换迷宫只会清除标记，只有前后两次点击的都是同一个算法才会刷新迷宫等等，这些完善的内容都不难，感兴趣的读者可以自行尝试。
课设有多个选题，在本题中，应当是我们组(还有一位组员也有参与本次课设)做的最充分。包括完善最终图形界面、算法的分析、算法思路的复述、关于整个课设的思考(自行思考想出的预处理方法，虽然复杂度高了点)、验收之前对所有可能提问的准备，尤其是提问，可以说老师问的我们都预演过，没问但可能问的也准备了，详细到某个算法中定义的一个变量作用是什么。课设验收时，整个回答过程很流畅。当然，老师的问题也不会很难，主要还是听清楚问的是什么，不要答非所问。
本系列到此结束，仅是记录个人的感想和向读者分享整个课设经历。
END在最后Lastbutnotleast
本文介绍了最后一种求解迷宫的方法，一种预处理的方法，即遍历矩阵，填充死胡同。感兴趣的读者可以尝试下，这种方法并不难实现。
本系列也到此结束，接下来将继续分享数据结构与算法的内容或是其他计科专业课的内容。
往期精彩回顾数据结构课程设计——迷宫求解(三)
数据结构课程设计——迷宫求解(四)
数据结构课程设计——迷宫求解(五)
计科练习生