migong.rar_最优路径

#include <iostream.h> #include <stdlib.h> #include <time.h>//因为要产生随机函数种子 #include <windows.h>//因为要用Sleep延时函数 #define MAX_X 20 //定义迷宫大小 #define MAX_Y 20 int maze[MAX_X][MAX_Y]; class stack_for_maze//迷宫行走路线存储专用栈类！ { private: struct node//结点用来记录压栈的迷宫坐标 { int x; int y; char direction; //上一步的行走方向（即如何来到这里的） → ← ↑ ↓ node* next; }; node* head; public: stack_for_maze()//构造函数 { head=NULL; } ~stack_for_maze()//析构函数 { node* p=head; while(head!=NULL) { head=head->next; delete p; p=head; } } //________________________________________ void push(int xx,int yy,char ddirection)//压栈，将坐标和行走方向压栈 { node* new_node; new_node=new node; if(new_node!=NULL) { new_node->x=xx; new_node->y=yy; new_node->direction=ddirection; new_node->next=NULL; if(head==NULL) head=new_node; else { new_node->next=head; head=new_node; } } else cout<<"\n因为内存分配失败导致本次压栈失败！！！\n"; } //________________________________________ node* pop(int& xx,int& yy)//出栈时带回栈顶元素坐标 { if(head!=NULL) { node* p=head; head=head->next; xx=p->x; yy=p->y; delete p; } else { cout<<"\n因为栈已空导致本次出栈失败\n"; } return head; } //________________________________________ void print()//输出栈内元素 { if(head!=NULL) { node* p=head; while(p!=NULL) { cout<<" "<<p->x<<" "<<p->y<<" "<<p->direction<<endl; p=p->next; } } else cout<<"\n栈为空，打印失败\n"; } }; //_______________________________________________________ void CreateMaze()//创建迷宫 { int max_way=MAX_X*MAX_Y;//产生通路的参数，值越大障碍越少 int x,y; for(x=0;x<MAX_X;x++) for(y=0;y<MAX_Y;y++) maze[x][y]=1; //先把迷宫全部设为墙壁 srand((unsigned)time(NULL));//随机函数种子发生器（以时间做参数） for(int i=0;i<=max_way;i++)//随机构建迷宫通路 { x=rand()%(MAX_X-2)+1; y=rand()%(MAX_Y-2)+1; maze[x][y]=0; } maze[1][1]=0;//入口 maze[MAX_X-2][MAX_Y-2]=0;//出口 maze[0][1]=8; maze[MAX_X-1][MAX_Y-2]=0; } //_________________________________________________________ void PrintMaze()//输出迷宫的当前状态 { int x,y; system("cls");//清屏 cout<<endl; for(x=0;x<MAX_X;x++) { for(y=0;y<MAX_Y;y++) { if(maze[x][y]==0){cout<<" ";continue;}//通路 if(maze[x][y]==1){cout<<"■";continue;}//墙 if(maze[x][y]==2){cout<<"×";continue;}//死胡同 if(maze[x][y]==3){cout<<"↓";continue;}//向下走 if(maze[x][y]==4){cout<<"→";continue;}//向右走 if(maze[x][y]==5){cout<<"←";continue;}//向左走 if(maze[x][y]==6){cout<<"↑";continue;}//向上走 if(maze[x][y]==7){cout<<"※";continue;}//当前站立位置 if(maze[x][y]==8){cout<<" ";continue;}//通路 } cout<<endl; } Sleep(200);//延时函数 } //_________________________________________________________ void move(stack_for_maze &s) { int x=1,y=1;//出发点 while(1) { maze[x][y]=2; //-----------------------向下探路 if(maze[x+1][y]==0)// ↓ { s.push(x,y,'D');//当前位置压栈 maze[x][y]=3;//将当前位置做一个向下的标记↓用代码3表示 x=x+1;//向下走到一个新位置 maze[x][y]=7;//标记当前站立位置为7，用符号※表示 PrintMaze(); if((x==MAX_X-1)&&(y==MAX_Y-2)) { s.push(x,y,'*'); cout<<"\n成功走出！！！\n"; return; } else continue; } //-----------------------向右探路 if(maze[x][y+1]==0)// → { s.push(x,y,'R');//当前位置压栈 maze[x][y]=4;//将当前位置做一个向右的标记→用代码4表示 y=y+1;//向右走到一个新位置 maze[x][y]=7;//标记当前站立位置为7，用符号※表示 PrintMaze(); if((x==MAX_X-1)&&(y==MAX_Y-2)) { s.push(x,y,'*'); cout<<"\n成功走出！！！\n"; return; } else continue; } //-----------------------向上探路 if(maze[x-1][y]==0)// ↑ { s.push(x,y,'U');//当前位置压栈 maze[x][y]=6;//将当前位置做一个向上的标记↑用代码6表示 x=x-1;//向上走到一个新位置 maze[x][y]=7;//标记当前站立位置为7，用符号※表示 PrintMaze(); if((x==MAX_X-1)&&(y==MAX_Y-2)) { s.push(x,y,'*'); cout<<"\n成功走出！！！\n"; return; } else continue; } //-----------------------向左探路 if(maze[x][y-1]==0)// ← { s.push(x,y,'L');//当前位置压栈 maze[x][y]=5;//将当前位置做一个向左的标记←用代码5表示 y=y-1;//向左走到一个新位置 maze[x][y]=7;//标记当前站立位置为7，用符号※表示 PrintMaze(); if((x==MAX_X-1)&&(y==MAX_Y-2)) { s.push(x,y,'*'); cout<<"\n成功走出！！！\n"; return; } else continue; } //--------------------上下左右均不通则回退，即出栈一次，如果出栈导致栈空则说明无路可走了！ if(s.pop(x,y)==NULL&&maze[x-1][y]!=0&&maze[x][y-1]!=0&&maze[x][y+1]!=0&&maze[x+1][y]!=0) { cout<<"\n没有找到合适路径！！！\n"; maze[0][1]=7;//没有找到路，就站在起点吧！ if(maze[1][1]!=1)maze[1][1]=2; return; } } } //_________________________________________________________ void main() { CreateMaze();//创建迷宫 PrintMaze();//输出当前迷宫的初始状态 stack_for_maze stack;//定义一个栈的对象，用来记录行走路线 move(stack);//行走中…… PrintMaze();//输出迷宫的最终状态 //stack.print(); }