迷宮第一階段  

/*****************************************************
                   WZ ASUST 2016
迷宮問題的兩種記錄形式
                 1：test11隊(duì)列  需要記錄后出隊(duì)列
                 2：test22棧實(shí)現(xiàn) 不需要彈出所記錄的坐標(biāo)（僅無支路時(shí)）
  第二種  不通過在循環(huán)中修改值的方法來展現(xiàn)路徑（但還是得先修改為1）
   可以在最后  彈出元素并修改所經(jīng)過的值為其他標(biāo)識(shí)
在寫文檔中發(fā)現(xiàn) 有支路時(shí)，就得寫彈出部分的代碼  彈出無解的坐標(biāo)
****************************************************/
#include<iomanip>//操縱運(yùn)算子 setw(2)
// 內(nèi)部矩陣大小 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;
//初始化隊(duì)列
int InitQueue(LinkQueue &Q)
{  
 Q.front=Q.rear=(Queueptr*)malloc(sizeof(QNode));
 if(!Q.front) return 0;
 Q.front->next=NULL;
 return 1;
}
 //坐標(biāo)x,y 入隊(duì)
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;
}
//坐標(biāo)x,y 出隊(duì)
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; //入口標(biāo)記為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;//建立一個(gè)棧  
MAZE[x][y]=1; //入口標(biāo)記為1
 s.push(x); s.push(y);
 MAZE[x][y]=1; //入口標(biāo)記為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中

棧實(shí)現(xiàn)基本都可以 走到支路 然后給支路置1  記錄一個(gè)棧長度 然后從新再來 得到新的棧 若短就更新棧  最后沒有路時(shí)就比較 是否有解 有解取最短棧就是最優(yōu)解