/*****************************************************WZASUST2016迷宫问题的两种记录形式1：test11队列需要记录后出队列2：test22栈实现不需要弹出所记录的坐标（仅无支路时）第二种不通过在循环中修改值的方法来展现路径（但还是得先修改为1）可以在最后弹出元素并修改所经过的值为其他标识在写文档中发现有支路时，就得写弹出部分的代码弹出无解的坐标****************************************************/#include<iomanip>//操纵运算子setw(2)//内部矩阵大小6*8加边框后是8*10#defineN20typedefintelem_type;classStack{public:Stack(){top=0;size=N;data=newelem_type[size];}~Stack(){top=0;delete[]data;data=NULL;}voidIncSize(){size=2*size;elem_type*p=newelem_type[size];memcpy(p,data,sizeof(elem_type)*top);delete[]data;data=p;}boolpush(elem_typevalue){if(isfull()){IncSize();}data[top++]=value;returntrue;}intgettop()//得到栈顶元素{returndata[--top];}boolisfull()//判断是否已满{returntop==size;}private:elem_type*data;inttop;intsize;};constintExitX=6;constintExitY=8;usingnamespacestd;typedefstructQNode{intx,y;structQNode*next;}QNode,Queueptr;typedefstruct{Queueptr*front;Queueptr*rear;}LinkQueue;//初始化队列intInitQueue(LinkQueue&Q){Q.front=Q.rear=(Queueptr*)malloc(sizeof(QNode));if(!Q.front)return0;Q.front->next=NULL;return1;}//坐标x,y入队intEnQueue(LinkQueue&Q,intx,inty){Queueptr*p;p=(Queueptr*)malloc(sizeof(QNode));if(!p)return0;p->x=x;p->y=y;p->next=NULL;Q.rear->next=p;Q.rear=p;return1;}//坐标x,y出队intDeQueue(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);return1;}intGetHead_x(LinkQueueQ,int*x){*x=Q.front->next->x;return*x;}intGetHead_y(LinkQueueQ,int*y){*y=Q.front->next->y;return*y;}intMAZE[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};//检查是否走到出口intchkExit(intx,inty,intex,intey){if(x==ex&&y==ey)return1;elsereturn0;}inttest11(){inti,j;intx=1;//入口inty=1;//入口for(i=0;i<8;i++){for(j=0;j<10;j++)cout<<setw(2)<<MAZE[i][j]<<"";cout<<endl;}LinkQueueQ;InitQueue(Q);MAZE[x][y]=1;//入口标记为1EnQueue(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;}return0;}inttest22(){inti,j;intx=1;//入口inty=1;//入口for(i=0;i<8;i++){for(j=0;j<10;j++)cout<<setw(2)<<MAZE[i][j]<<"";cout<<endl;}Stacks;//建立一个栈MAZE[x][y]=1;//入口标记为1s.push(x);s.push(y);MAZE[x][y]=1;//入口标记为1s.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;}return0;}voidnewMAZE1(){time_tt;srand((unsigned)time(&t));intk=0;intr,l;while(k<20){r=rand()%8;l=rand()%10;if(MAZE[r][l]!=0){MAZE[r][l]=0;k++;}}}voidnewMAZE(){intk=0;while(k<8){MAZE[k][1]=0;k++;}k=0;while(k<10){MAZE[6][k]=0;k++;}}intmain(){test11();cout<<endl;newMAZE();cout<<endl;test22();return0;}//修bug中

栈实现基本都可以 走到支路 然后给支路置1 记录一个栈长度 然后从新再来 得到新的栈 若短就更新栈 最后没有路时就比较 是否有解 有解取最短栈就是最优解