c++编迷宫设置通路的思路

显示全部楼层 · 2011-1-28 06:57:31

我们有个大作业是用C++写个迷宫的，我遇到了问题。
我现在的思路是：我用#代替墙，用。代替可走的路；
我先建立一个动态二维数组，然后全部元素写入#，
再随机弄个入口和出口。（这些都没问题了）
问题是从入口到出口的这条通路的设置。
我是按照网上的一种思路：就是从入口开始不停的随机向四个方向走，直到可以到出口为止，这样也是可以的。（走的时候会吧#变成。）
问题出来了-------因为是随机的向四个方向走，所以在一片区域内。很多，而在另一片区域内#又很多，很明显的两极分化，虽然有通路了。但是这样很怪啊。
又什么办法可以改变一下吗？
或者说有其他的思路？
谢谢。！求助啊！

千问 · 2011-1-28 06:57:31

#includeusing namespace std;class T
//定义描述迷宫中当前位置的结构类型{public: int x;
//x代表当前位置的行坐标 int y;
//y代表当前位置的列坐标 int dir;
//0:无效,1:东,2:南,3:西,4:北};class LinkNode
//链表结点{ friend class Stack;public: T data; LinkNode *next;};class Stack{private: LinkNo

千问 · 2011-1-28 06:57:31

你用的是回溯法，估计你是想要实现最短通路。我给出一种思路。在一幅无向图中，如果所有的边都有相同的权，要求解某点到其他点的最短路径可以用迪杰斯特拉算法，也可以用广度优先遍历的方法。广度优先遍历的生成树即为树根到其他顶点的最短路径。相对于迪杰斯特拉算法其时间复杂度为O(n)。余下的问题就是怎么将迷宫抽象成无向图了。方法是对二维迷宫中的每一个“。”编号，从1起，采

千问 · 2011-1-28 06:57:31

把你的设计思路改改，从开口开始随机走的时候，第一步随机，从第二步开始，只能随机向3个方向走，就是不能走回上一步的位置，这样会好点；

千问 · 2011-1-28 06:57:31

请参考：不要随机的向四个方向走第一个只能下边左边第二个下边右边之类的错开

千问 · 2011-1-28 06:57:31

才10分求助个腿。你不希望得到的回答就只有10分含金量吧。