|
?
所谓规则，就是矩形，路线唯一，
所谓满，就是不能在原地图里再增加路或者分支，不会出现达不到的地方
如下例图：
█████████████████
█ █ █
█ ███ ███ █████ █
█ █ █ █ █
█ █ ███████ █ █ █
█ █ █ █ █
█ ███████ █ █████
█ █ █ █ █
█ █ ███████ ███ █
█ █ █ █
█ ███████ █████ █
█ █ █ █ █
███ █ █ ███████ █
█ █ █ █ █
█ ███ ███ █ █████
█ █
█████████████████
?
简单的来说，就是平面图的任意生成树问题，先讲个简单点的生成算法：随机DFS
用这个算法，生成的迷宫的特点是，分支不多，但往往很深，难度较大。
生成的代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAZE_MAX????50
char map[MAZE_MAX+2][MAZE_MAX+2];
int search(int x,int y)
{
????static int d[4][2]={0,1,-1,0};
????int zx=x*2,zy=y*2,next,turn,i;
????map[zx][zy]=1; turn=rand()%2? 1:3;
????for(i=0,next=rand()%4;i<4;i++,next=(next+turn)%4)
????????if(map[zx+2*d[next][0]][zy+2*d[next][1]]==0)
????????????map[zx+d[next][0]][zy+d[next][1]]=1,
????????????search(x+d[next][0],y+d[next][1]);
????return 0;
}
void Make_Maze(int x,int y)
{
????int z1,z2;
????for(z1=0,z2=2*y+2;z1<=2*x+2;z1++)map[z1][0]=1,map[z1][z2]=1;
????for(z1=0,z2=2*x+2;z1<=2*y+2;z1++)map[0][z1]=1,map[z2][z1]=1;
????map[1][2]=1;map[2*x+1][2*y]=1;??srand((unsigned)time(NULL));
????search(rand()%x+1,rand()%y+1);
}
int main(void)
{
????int x=8,y=8,z1,z2; //x和y的值指定了这个要生成的迷宫的大小
????Make_Maze(x,y);
????for(z2=1;z2<=y*2+1;z2++){
????????for(z1=1;z1<=x*2+1;z1++) fputs(map[z1][z2]?" ":"█",stdout);
????????if(z2<=y*2)putchar(10);
????}
????return 0;
}
复杂度O(xy)，唯一缺点是这个代码用递归，在迷宫较大时，可能出现栈溢出，
要是需要生成大迷宫，就自己模拟栈即可。
代码变形：
为了使生成出来的地图更好看，像以下这种：
━━━━┳━━━┳━━━━━━━━━━━┓
┃ ┃ ┃
┃ ┃ ┃ ┃ ┃ ━━┓ ┏━━━━ ┃
┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ ┃ ┃ ┗━━━┳━┛ ┃ ┏━━━┫
┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ ┗━┻━┳━━ ┃ ┏━┫ ┗━┓ ┃
┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ ━━┓ ┃ ┏━┛ ┃ ┗━┓ ┃ ┃
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┣━━ ┃ ┃ ┃ ━━┫ ┃ ┃ ┃ ┃
┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ ━━┻━┳━┫ ┃ ┣━┛ ┣━━ ┃
┃ ┃ ┃ ┃ ┃ ┃ ┃
┣━━━━ ┃ ┗━┛ ┃ ━━┛ ━━┛
┃ ┃ ┃
┗━━━━━┻━━━━━┻━━━━━━━━
要做到这种效果，其实我们只要在原来代码的输出的地方做一点手脚：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
char cw[][4]={" ","┃","━","┗","┏","┣",
??????????????"━","┛","┻","┓","┫","┳","╋"
?????????????};
char m[50][50];
char* getw(int x,int y)
{
????return cw[(m[x][y-1]?0:1)|(m[x+1][y]?0:2)|(m[x][y+1]?0:4)|(m[x-1][y]?0:8)];
}
int sr(int x,nx,tn=rand()%2? 1:3,i;
????m[zx][zy]=1;
????for (i=0,nx=rand()%4;i<4;i++,nx=(nx+tn)%4)
????????if (m[zx+2*d[nx][0]][zy+2*d[nx][1]]==0)
????????????m[zx+d[nx][0]][zy+d[nx][1]]=1,sr(x+d[nx][0],y+d[nx][1]);
????return 0;
}
void Make_Maze(int x,z2;
????for (z1=0,z2=2*y+2;z1<=2*x+2;z1++)m[z1][0]=1,m[z1][z2]=1;
????for (z1=0,z2=2*x+2;z1<=2*y+2;z1++)m[0][z1]=1,m[z2][z1]=1;
????m[1][2]=1;m[2*x+1][2*y]=1;
????srand((unsigned)time(NULL));
????sr(rand()%x+1,rand()%y+1);
}
int main(void)
{
????int x=10,z2;Make_Maze(x,y);
????for (z2=1;z2<=y*2+1;z2++)
????{
????????for (z1=1;z1<=x*2+1;z1++)printf(m[z1][z2]?" ":getw(z1,z2));
????????if (z2<=y*2)putchar(10);
????}
????return 0;
}
? （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
