/*

 使用BFS解决迷宫问题

 **/

 #include<iostream>

 #include<queue>

 #include<vector>

 using namespace std;

 struct MaNode{

     int x;

     int y;

     MaNode *pre;

     MaNode(int x1=,int y1=,MaNode *p =NULL ):x(x1),y(y1),pre(p)

     {

     }

 };

 const int maxr=;

 const int maxc=;

 queue<MaNode*> qmaze;

 vector<MaNode*> vemaze; //保存节点，以便释放

 int maze[maxr][maxc] = {

     ,,,,,

     ,,,,,

     ,,,,,

     ,,,,,

     ,,,,,

  };

 void visit(int x,int y, MaNode *p )  //访问节点

 {

     struct MaNode *p2 = new MaNode(x,y,p);

     //p2->x = x;

     //p2->y =y;

     //  p2->pre = p;

      maze[x][y] = ; //标识已经访问

     qmaze.push(p2);

 }

 void bfs() // 宽度优先搜索

 {

     MaNode *head = new MaNode;

     qmaze.push(head);

     while( !qmaze.empty() )

     {

         MaNode *p= qmaze.front();

         //int x=  p->x+1;

         //int y= p->y+1;

         vemaze.push_back(p);

         qmaze.pop();

         if( p->x ==maxr- && p->y==maxc- )

         {

              break;

         }

         if(p->x + <=maxr  && maze[p->x+][p->y] ==  )

         {

             visit(p->x+,p->y,p);

         }

         if(p->y+ <=maxc&& maze[p->x][p->y+] == )

         {

           visit(p->x,p->y+,p);

         }

        if( p->x- >=  && maze[p->x-][p->y] == )

        {

        visit(p->x-,p->y,p);

        }

       if( p->y- >=  && maze[p->x][p->y-] == )

        {

        visit(p->x,p->y-,p);

        }

     }

 }

 void printPath()  //打印路径

 {

     MaNode *p  = vemaze[vemaze.size()-];

     while( p != NULL )

     {

         cout<<"("<<p->x<<","<<p->y<<")"<<endl;

         p=p->pre;

     }

     //cout<<endl;

 }

 void destroy()  //销毁节点

 {

     for(size_t  i=; i<vemaze.size() ; i++ )

     {

         delete vemaze[i];

     }

 }

 int main()

 {

     bfs();

     printPath();

    destroy();

    return ;

 }