仙剑五九黎祠的九宫格对于我这种没有窍门,没有经验的人来说还真是挺难为我的.
一开始左右两个目的地我竟然神乎其技地蒙过去了
,最后要到达对面我试了很久都通不过,我知道网上肯定已经有解法了,可是就这么放弃总有点不甘心啊!所以我就开始试着编写一个程序让计算机为我解开这个迷宫.
进行广度优先搜索,就是试探上下左右一次移动能否拼出从起点到终点有通路的图,要是不行的话就递归进入第二步再次试探.
判断是否有一条通路的思路如下
这个九宫格里边有两块的出入口在1/4分界线处,所以我打算把每个宫格分割为4*4的小块,这样来取点和边
这样,九宫格最多有13*13个点,然后依据目前九宫格的图样绘出各条边,比如上图(2,0)到(4,2)有边,这只要扫描每个宫格内的边(事先存储好)就行,在一个169*169的图中标记好各条边
从起点出发遍历他它能到达的点,新加入的点能到达的点也是起点能到达的点,循环更新,一直到终点被加入(成功的找到一种移动步骤),或者没有新的点可加入(按这个步骤移动后还不能找到那条通路).
程序运行结果如下:
注意这里的上下左右是指这次应该点击相对于空白宫格的哪个方位的宫格
第一行是从起点到左边的步骤
第二行是从起点到右边的步骤(都是在重置原始状态下开始的)
第三行是从起点到上边的步骤(后来发现这时正好左右也可以到达)
程序的时间复杂度是O(3^deep),空间复杂度也是O(3^deep),所以程序在100毫秒内执行完毕让我很欣慰
从起点到上边共递归了11层,程序占用了5M内存,如果再深几层的话我的2G内存也不够它吃的
由于使用的是一层一层的广度优先搜索,所以以上步骤是最少的有木有
以上三种走法结果如下图:
上 右
上 左 上 右 右 下 左 左
右 上 上 左 下 下 右 上 左 左 上
我热爱自由软件,我喜欢公布我的源代码
都是标准的C程序有木有,其实我还没学C++,不然栈不用自己写了
#include
#include
#include
#define MAXDIAN 5
#define MAXBIAN 4
#define MAXDEEP 22
typedef struct Dian{int x,y;}dian;
typedef struct Bian{int a,b;}bian;
typedef struct GongGe{
dian d[MAXDIAN];
bian b[MAXBIAN];
}gongge;
typedef struct Node{
char his[MAXDEEP];
char sx,sy;
char gong[3][3];
struct Node *next;
}node,*lnode;
char dians[13*13];
char map[169][169];
dian start,end;
gongge kuai[]={
{
{
{0,0},
},
{
{0,0},
}
},{
{
{2,0},{4,2},{2,4},
},
{
{0,1},{0,2},{1,2},
}
},{
{
{0,1},{0,3},
},
{
{0,1},
}
},{
{
{2,0},{0,2},{2,4},
},
{
{0,1},{0,2},{1,2},
}
},{
{
