C++迷宫的实现代码

 //文件的输入，有墙 #include #include #include #include using namespace std; const int max1=100*100;   //加入墙 const int max2=102; bool value[max2][max2];   //记录是否被访问过 int maze[max2][max2];    //迷宫的大小 int n,m;   //输入迷宫的长和宽 ofstream outfile("path.txt");   //文件保存迷宫及输出的路径 struct Point   //栈中的数据 { int x; int y; }; struct Stack { int top; Point path[max1];  //存坐标点的数组栈 stack() { top=-1;    //栈中从0开始存数据 } bool Empty()  //检验是否为空 { if(top==-1)return true; else return false; } void Clear()   //清空栈 { top=-1; } void Push(Point p)   //进栈 { top++; path[top]=p; } Point Pop()    //返回栈顶元素 { return path[top]; } void Delete_Pop()   //删除顶栈元素 { top--; } int Y_N_Push() { int x=path[top].x; int y=path[top].y; if(x<1||yn||y>m||!value[x][y]||maze[x][y])    //不符合要求 { value[x][y]=false;   //标记这个点被访问过（不能任意做标记） return 1; } else if((x==n)&&(y==m))   //已经找到出口，不要标记，后面直接跳出 return 2; else { value[x][y]=false;   //标记这个点被访问过 return 3;    //可以进栈 } } void Output()   //输出栈中的路径 { int i; for(i=0;i<top;i++) { cout<<"("<<path[i].x<<","<<path[i].y<<")"<"; } cout<<"("<<path[i].x<<","<<path[i].y<<")"<<endl; outfile<<"该迷宫的路径为:"<<endl;   //文件的输出 for(i=0;i<top;i++) { outfile<<"("<<path[i].x<<","<<path[i].y<<")"<"; } outfile<<"("<<path[i].x<<","<<path[i].y<<")"<<endl; } }; Stack stack;     //不可以放在栈的定义前面 bool Test_value()     //检验每个节点是否是否被访问过，全访问过了则为true，false为没有全部访问过 { int i,j; bool t=true; for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(value[i][j]!=false) { t=false; break; } return t; } int Judge() { Point t; int frage=0;    //先规定先向右 while(frage==0) { t=stack.Pop();   //返回栈顶元素 t.y=t.y+1;   //向右 stack.Push(t); if(stack.Y_N_Push()==1)   //不符合要求的节点 { stack.Delete_Pop(); t=stack.Pop(); t.x=t.x+1;      //向下 stack.Push(t); if(stack.Y_N_Push()==1) { stack.Delete_Pop(); t=stack.Pop(); t.y=t.y-1;     //向左 stack.Push(t); if(stack.Y_N_Push()==1) { stack.Delete_Pop(); t=stack.Pop(); t.x=t.x-1;    //向上 stack.Push(t); if(stack.Y_N_Push()==1) { frage=4;    //这个点4个方向都不成立 stack.Delete_Pop(); } } } } if(stack.Y_N_Push()==2) { frage=5;    //找到了出口并跳出 break; } } return frage; } void Search() { stack.Clear(); Point u; u.x=1; u.y=1; stack.Push(u); value[1][1]=false; while(true) { int t=Judge(); if(t==5)   //找到了路 { cout<<"找到了能通的路，路径为(用那个点的坐标表示):"<<endl; stack.Output(); break; } if(t==4)stack.Delete_Pop();   //退回一个点继续找 if((Test_value()==true)||(stack.top==-1))   //很重要的条件，stack.top==-1，否则的话当有个点四周都不能通过的话，而且前面的点也不能通的话，就没有通路 { cout<<"没有通路!"<<endl; outfile<<"没有通路!"<<endl; break; } } } int main() { int i,j; cout<>n>>m; for(i=0;i<=(m+1);i++) maze[0][i]=maze[n+1][i]=1; for(i=1;i<=(n+1);i++) maze[i][0]=maze[i][m+1]=1; cout<<"输入迷宫，1为墙，0为可通路(规定左上角为入口，右下角为出口):"<<endl; srand(unsigned(time(NULL))); for(i=1;i<=n;i++) for(j=1;j<=m;j++) maze[i][j]=(rand()%2); maze[1][1]=maze[n][m]=0; cout<<"输入的迷宫(带有墙)是:"<<endl; for(i=0;i<=(n+1);i++) { for(j=0;j<=(m+1);j++) cout<<maze[i][j]<<" "; cout<<endl; } if(!outfile) { cerr<<"open error!"<<endl; exit(1); } outfile<<"生成"<<n<<"行"<<m<<"列"<<"的迷宫为:"<<endl; for(i=0;i<=(n+1);i++) { for(j=0;j<=(m+1);j++) outfile<<maze[i][j]<<" "; outfile<<endl; } for(i=1;i<=n;i++)   //记录从value[0][0]开始 for(j=1;j<=m;j++) value[i][j]=true; Search(); return 0; }