【D降调C#】天草迷宫独特算法

代码下载

因为实验要求写迷宫算法的缘故，不得不研究一下这个看似没用的东西。实验要求上有提示算法思路，还有伪代码（本人灰常反感。。。代码都给了，当我白痴啊？）。老师上课也讲了思路，但是我一下子没听懂。然后就不听了。伪代码也懒得去看。自己想吧。书上给的算法是堆栈，递归，路过标记，死路回头，当然少不了几个结构。

下面说说我的算法，我的大思路是：把通路留住把死路消灭。可以想象一下，0代表通路，1代表墙。那既然通路都给我们了，我们只需将死路灭掉，当然，如果迷宫本来设计就走不通的话。那只会剩下出入口。

1、判断死路的方法

迷宫是个二维数组，周围有一圈墙。如，题目给的迷宫是10X10的话这里要定义一个12X12的二维数组，并且外围赋值1。节点可以向八个方向试探。

先定义节点结构，如图

紫色为零，可走通

代码：

class Node

{

public int[] D = new int[8];//方向数组

public int x;//当前Node在迷宫数组的坐标

public int y;

}

死路即为只有一条后路的节点，有两种情况：

1、斜方向（1，3，5，7都是斜方向）

2、直方向（0，2，4，6都是直方向）

通过观察可以发现，当前节点周围有7堵墙，即7个1。也可以判断连续五个方向为1。

满足上述条件的当前节点置为1（迷宫数组置为1），如此循环死路就会一个个消失。

代码：

private void T_天草必杀()

{

int count = 0;//记录8方向通路的个数

for (int i = 0; i < 10; i++)

for (int j = 0; j < 10; j++)

{

count = 0;

if ((i != P_入口.X && j != P_入口.Y) || (i != P_出口.X && j != P_出口.Y))//出入口不处理

{

F_赋值tmpNode(i, j);

for (int k = 0; k < 8; k++)

{

if (tmpNode.D[k] == 48)//48为"0"的数值，即通路。49为"1"，懒得处理了- -！

count++;

}

if (count < 2)

{

maze[i + 1, j + 1] = 49;

}

}

}//遍历MAZE

}

当然，这里显然没有考虑大路（当前节点有一条以上的通路）的情况。好，下面这循环搞定大路。经过下面这个循环，迷宫只会剩下上面那两种情况。

2、消灭大路（非大陆啊，看清楚，别说我反国家啊）

像这种情况叫大路，人眼观察为死路，要消灭的。

判断方法：当0，2（2，4）方向为墙，5（7）方向为通路 即置为死路。

0，2，5方向为一组。2，4，7方向为一组，4，6，1方向为一组，6，0，3方向为一组

代码：

private void Find_a_way()

{

for (int i = 0; i < 10; i++)

for (int j = 0; j < 10; j++)

{

if ((i != P_入口.X && j != P_入口.Y) || (i != P_出口.X && j != P_出口.Y))

{

F_赋值tmpNode(i, j);

if ((tmpNode.D[0] == 48 && tmpNode.D[2] == 48 && tmpNode.D[5] == 49) ||

(tmpNode.D[2] == 48 && tmpNode.D[4] == 48 && tmpNode.D[7] == 49) ||

(tmpNode.D[4] == 48 && tmpNode.D[6] == 48 && tmpNode.D[1] == 49) ||

(tmpNode.D[6] == 48 && tmpNode.D[0] == 48 && tmpNode.D[3] == 49))//精髓- -！

maze[i + 1, j + 1] = 49;

}

}//遍历MAZE

}

这里提醒一点，这个函数不要对出入口判断。因为出入口一大半是墙（参见定义的二维数组）

注意：

经过这个循环，迷宫就剩下前面所说的两种路了。写思路是先T_天草必杀()后Find_a_way()，实际是操作是先Find_a_way()后T_天草必杀()的。这个算法经过老师的检验的，没问题。

有些细节用不同的语言的童鞋改一下

如果觉得《【D降调C#】天草迷宫独特算法》对你有帮助，请点赞、收藏，并留下你的观点哦！