【软件开发综合实验】迷宫游戏Ⅱ

//¡õ;¡ö #include<cstdio> #include<algorithm> #include<cstdlib> #include<ctime> #include<cstring> #include<queue> #include<windows.h> #include<conio.h> using namespace std; struct Edge{ int u,v; Edge(){} Edge(const int &u,const int &v){ this->u=u; this->v=v; } }edges[2005]; const int dx[]={0,1,0,-1},dy[]={1,0,-1,0}; int dxx[100],dyy[100]; typedef pair<int,int> Point; int b[45][45]; int fa[2005],id[25][25],n,m,idx[405],idy[405]; bool vis[45][45]; Point pre[45][45]; int findroot(int x);//并查集找根，路径压缩 Point getmid(int x1,int y1,int x2,int y2);//求中点 void makemap();//利用kruscal算法随机生成地图 void findpath();//使用BFS算法自动寻路 void show();//显示地图 int main(){ char ch; dxx[72]=-1; dyy[72]=0; dxx[80]=1; dyy[80]=0; dxx[75]=0; dyy[75]=-1; dxx[77]=0; dyy[77]=1; int op; srand(time(0)); while(1){ system("cls"); printf("\n\n\t\tWelcome to the maze game! Please choose the option you want."); printf("\n\n\t\t1.Generate a maze and find the path automatically."); printf("\n\n\t\t2.Generate a maze and play the game."); printf("\n\n\t\t"); scanf("%d",&op); if(op==1){//自动寻路 system("cls"); printf("\n\n\t\tPlease input the size of the maze (no more than 20)."); printf("\n\n\t\t"); scanf("%d",&n); if(n>20){ n=20; } makemap(); findpath(); system("cls"); show(); printf("\n\n\t\t按任意键返回"); while(!kbhit()); ch=getch(); if(ch==-32){ getch(); } } else if(op==2){//实现交互 system("cls"); printf("\n\n\t\tPlease input the size of the maze (no more than 20)."); printf("\n\n\t\t"); scanf("%d",&n); if(n>20){ n=20; } makemap(); int x=2*n-1,y=2*n-1; b[2*n-1][2*n-1]=3; while(1){ system("cls"); show(); if(x==0 && y==1){ printf("\n\n\t\tYou win!\n\t\t按任意键返回"); b[0][1]=1; while(!kbhit()); ch=getch(); if(ch==-32){ getch(); } break; } while(1){ while(1){ while(!kbhit()); ch=getch(); if(ch==-32){ ch=getch(); break; } } int tx=x+dxx[ch],ty=y+dyy[ch]; if(b[tx][ty]==1){ b[tx][ty]=3; b[x][y]=1; x=tx; y=ty; break; } } } } } return 0; } void show(){ printf("\n\n"); for(int i=0;i<=2*n;++i){ printf("\t\t"); for(int j=0;j<=2*n;++j){ printf(b[i][j]==1 ? "□" : (b[i][j]==0 ? "■" : (b[i][j]==2 ? "○" : "●"))); } puts(""); } } void findpath(){ queue<Point>q; memset(vis,0,sizeof(vis)); q.push(Point(2*n-1,2*n-1)); vis[2*n-1][2*n-1]=true; while(!q.empty()){ Point U=q.front(); q.pop(); for(int i=0;i<4;++i){ int tx=U.first+dx[i],ty=U.second+dy[i]; if(b[tx][ty]==1 && !vis[tx][ty]){ pre[tx][ty]=U; if(Point(tx,ty)==Point(0,1)){ goto OU; } vis[tx][ty]=true; q.push(Point(tx,ty)); } } } OU: Point U=Point(0,1); b[0][1]=2; while(U!=Point(2*n-1,2*n-1)){ U=pre[U.first][U.second]; b[U.first][U.second]=2; } } void makemap(){ int pen=0; for(int i=1;i<=n*n;++i){ fa[i]=i; } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ id[i][j]=++pen; idx[pen]=2*i-1; idy[pen]=2*j-1; } } m=0; for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ for(int k=0;k<2;++k){ int tx=i+dx[k],ty=j+dy[k]; if(tx>=1 && tx<=n && ty>=1 && ty<=n){ edges[++m]=Edge(id[i][j],id[tx][ty]); } } } } random_shuffle(edges+1,edges+m+1); memset(b,0,sizeof(b)); int tot=0; for(int i=1;i<=m;++i){ int f1=findroot(edges[i].u),f2=findroot(edges[i].v); if(f1!=f2){ Point mid=getmid(idx[edges[i].u],idy[edges[i].u],idx[edges[i].v],idy[edges[i].v]); b[idx[edges[i].u]][idy[edges[i].u]]= b[idx[edges[i].v]][idy[edges[i].v]]= b[mid.first][mid.second]=1; fa[f1]=f2; ++tot; if(tot==n*n-1){ break; } } } b[0][1]=1; if(n==1){ b[1][1]=1; } } int findroot(int x){ return fa[x]==x ? x : fa[x]=findroot(fa[x]); } Point getmid(int x1,int y1,int x2,int y2){ return Point(x1+x2>>1,y1+y2>>1); }