您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
/***************************************************** WZ ASUST 2016 迷宫问题的两种记录形式 1:test11队列 需要记录后出队列 2:test22栈实现 不需要弹出所记录的坐标(仅无支路时) 第二种 不通过在循环中修改值的方法来展现路径(但还是得先修改为1) 可以在最后 弹出元素并修改所经过的值为其他标识 在写文档中发现 有支路时,就得写弹出部分的代码 弹出无解的坐标 ****************************************************/ #include<iomanip>//操纵运算子 setw(2) // 内部矩阵大小 6*8 加边框后是8*10 #define N 20 typedef int elem_type; class Stack { public: Stack() { top = 0; size = N; data = new elem_type[size]; } ~Stack() { top = 0; delete []data; data = NULL; } void IncSize() { size = 2*size; elem_type *p = new elem_type[size]; memcpy(p,data,sizeof(elem_type)*top); delete []data; data = p; } bool push(elem_type value) { if(isfull()) { IncSize(); } data[top++] = value; return true; } int gettop()//得到栈顶元素 { return data[--top]; } bool isfull()//判断是否已满 { return top == size; } private: elem_type* data; int top; int size; }; const int ExitX=6; const int ExitY=8; using namespace std; typedef struct QNode { int x,y; struct QNode *next; }QNode,Queueptr; typedef struct { Queueptr *front; Queueptr *rear; }LinkQueue; //初始化队列 int InitQueue(LinkQueue &Q) { Q.front=Q.rear=(Queueptr*)malloc(sizeof(QNode)); if(!Q.front) return 0; Q.front->next=NULL; return 1; } //坐标x,y 入队 int EnQueue(LinkQueue &Q,int x,int y) { Queueptr *p; p=(Queueptr*)malloc(sizeof(QNode)); if(!p) return 0; p->x=x; p->y=y; p->next=NULL; Q.rear->next=p; Q.rear=p; return 1; } //坐标x,y 出队 int DeQueue(LinkQueue &Q,int *x,int *y) { Queueptr *p; p=Q.front->next; *x=p->x; *y=p->y; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); return 1; } int GetHead_x(LinkQueue Q,int *x) { *x=Q.front->next->x; return *x; } int GetHead_y(LinkQueue Q,int *y) { *y=Q.front->next->y; return *y; } int MAZE[8][10]={ 1,1,1,1,1,1,1,1,1,1, 1,0,0,0,1,1,1,1,1,1, 1,1,1,0,1,1,0,0,1,1, 1,1,1,0,1,1,0,0,1,1, 1,1,1,0,0,0,0,1,1,1, 1,1,1,1,1,1,0,1,1,1, 1,1,1,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1}; // 检查是否走到出口 int chkExit(int x,int y,int ex,int ey) { if(x==ex && y==ey) return 1; else return 0; } int test11(){ int i,j; int x=1; //入口 int y=1; //入口 for(i=0;i<8;i++) { for(j=0;j<10;j++) cout<<setw(2)<<MAZE[i][j]<<" "; cout<<endl; } LinkQueue Q; InitQueue(Q); MAZE[x][y]=1; //入口标记为1 EnQueue(Q,x,y); // while(1) { x=GetHead_x(Q,&x); y=GetHead_y(Q,&y); if(chkExit(x,y,ExitX,ExitY)==1) break; else{ if(MAZE[x-1][y]==0) { MAZE[x-1][y]=MAZE[x][y]+1; EnQueue(Q,(x-1),y); } if(MAZE[x+1][y]==0) { MAZE[x+1][y]=MAZE[x][y]+1; EnQueue(Q,(x+1),y); } if(MAZE[x][y-1]==0) { MAZE[x][y-1]=MAZE[x][y]+1; EnQueue(Q,x,(y-1)); } if(MAZE[x][y+1]==0) { MAZE[x][y+1]=MAZE[x][y]+1; EnQueue(Q,x,(y+1)); } else { DeQueue(Q,&x,&y); } } } cout<<"[test11 所求最短路径!]"<<endl; for(i=0;i<8;i++) { for(j=0;j<10;j++) cout<<setw(2)<<MAZE[i][j]<<" "; cout<<endl; } return 0; } int test22() { int i,j; int x=1; //入口 int y=1; //入口 for(i=0;i<8;i++) { for(j=0;j<10;j++) cout<<setw(2)<<MAZE[i][j]<<" "; cout<<endl; } Stack s;//建立一个栈 MAZE[x][y]=1; //入口标记为1 s.push(x); s.push(y); MAZE[x][y]=1; //入口标记为1 s.push(x); s.push(y); while(1) { y=s.gettop(); x=s.gettop(); if(chkExit(x,y,ExitX,ExitY)==1) break; else{ if(MAZE[x-1][y]==0) { MAZE[x-1][y]=MAZE[x][y]+1; s.push(x-1); s.push(y); } if(MAZE[x+1][y]==0) { MAZE[x+1][y]=MAZE[x][y]+1; s.push(x+1); s.push(y); } if(MAZE[x][y-1]==0) { MAZE[x][y-1]=MAZE[x][y]+1; s.push(x); s.push(y-1); } if(MAZE[x][y+1]==0) { MAZE[x][y+1]=MAZE[x][y]+1; s.push(x); s.push(y+1); } } } cout<<"[ test22 所求最短路径!]"<<endl; for(i=0;i<8;i++) { for(j=0;j<10;j++) cout<<setw(2)<<MAZE[i][j]<<" "; cout<<endl; } return 0; } void newMAZE1() { time_t t; srand((unsigned)time(&t)); int k=0; int r,l; while(k<20) { r=rand()%8; l=rand()%10; if(MAZE[r][l]!=0) { MAZE[r][l]=0;k++;} } } void newMAZE() { int k=0; while(k<8) { MAZE[k][1]=0;k++; } k=0; while(k<10) { MAZE[6][k]=0;k++; } } int main() { test11(); cout<<endl; newMAZE(); cout<<endl; test22(); return 0; } //修bug中
栈实现基本都可以 走到支路 然后给支路置1 记录一个栈长度 然后从新再来 得到新的栈 若短就更新栈 最后没有路时就比较 是否有解 有解取最短栈就是最优解
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。