注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

www.SolPie.net

2012年原创V家专辑「战国图」coming

 
 
 

日志

 
 

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

2009-12-26 12:13:22|  分类: C# |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

代码下载

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

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


1、判断死路的方法

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

先定义节点结构,如图

【D降调C】天草迷宫独特算法 - solpie - Solpie

紫色为零,可走通

代码:

class Node
        {
            public int[] D = new int[8];//方向数组
            public int x;//当前Node在迷宫数组的坐标
            public int y;
        }

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

1、斜方向【D降调C】天草迷宫独特算法 - solpie - Solpie(1,3,5,7都是斜方向)

2、直方向【D降调C】天草迷宫独特算法 - solpie - Solpie(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、消灭大路(非大陆啊,看清楚,别说我反国家啊)

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

【D降调C】天草迷宫独特算法 - solpie - Solpie

判断方法:当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_天草必杀()的。这个算法经过老师的检验的,没问题。

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

我要啦免    费统计
  评论这张
 
阅读(502)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017