迷宫第一阶段  

/*****************************************************                    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  记录一个栈长度 然后从新再来 得到新的栈 若短就更新栈  最后没有路时就比较 是否有解 有解取最短栈就是最优解